1.滑动窗口最大值

考察双端队列的使用
1.右边进，左边出，左边元素始终维护队列的最大值
Deque deque = new LinkedList<>(); // 定义双端队列
deque.peekLast() deque.peekFirst() 获取首尾元素
deque.addLast() deque.addFirst() 添加元素
deque.removeLast() deque.removeFirst() 删除元素

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] res = new int[nums.length-k+1];
        Deque<Integer> deque = new LinkedList<>();
        int index = 0;

        for (int i = 0; i < nums.length; i++) {
            // push
            while (!deque.isEmpty() && nums[i] > deque.peekLast()) {
                deque.removeLast();
            }
            deque.addLast(nums[i]);
            // pop
            if (i-k>=0 && nums[i-k] == deque.peekFirst()) {
                deque.removeFirst();
            }
            // res
            if (i-k+1>=0) {
                res[index] = deque.peekFirst();
                index++; 
            }
        }
        return res;
    }
}

2.最小覆盖子串（跳过）**

3.最大子数组和

考察贪心算法实现
极小值的表示：Integer.MIN_VALUE

class Solution {
    public int maxSubArray(int[] nums) {
        int maxRes = Integer.MIN_VALUE;  // 初始化成极小值
        int curRes = 0;

        for (int num : nums) {
            curRes += num;
            maxRes = Math.max(maxRes, curRes);
            if (curRes < 0) {
                curRes = 0;
            }
        }
        return maxRes;
    }
}

4.合并区间

考察区间的合并
Arrays.sort(arr, (a,b)->a[0]-b[0]) 排序第一个元素
list.get(list.size()-1);获取集合的最后一个元素
list.toArray(new int[list.size()][]) 集合转数组元素

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0]-b[0]);
        List<int[]> list = new ArrayList<>();
        list.add(intervals[0]);

        for (int i = 1; i < intervals.length; i++) {
            int[] lastElem = list.get(list.size()-1);
            if (lastElem[1] >= intervals[i][0]) {
                lastElem[1] = Math.max(lastElem[1], intervals[i][1]);
            } else {
                list.add(intervals[i]);
            }
        }
        return list.toArray(new int[list.size()][]);
    }
}

5.轮转数组

考察转圈，k = k % nums.length
主要还是双指针的应用

class Solution {
    public void rotate(int[] nums, int k) {
         k =k % nums.length;
        reverse(nums, 0, nums.length-1);
        reverse(nums, 0, k-1);
        reverse(nums, k, nums.length-1);
    }

    public void reverse(int[] nums, int left, int right) {
        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
}

6.除自身以外数组的乘积

前缀积和后缀积的使用
计算除这个元素以外的前缀积和后缀积，他们相乘就是结果

class Solution {
    public int[] productExceptSelf(int[] nums) {
        // 前缀积和后缀积
        int[] pre = new int[nums.length];
        pre[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            pre[i] = pre[i-1] * nums[i-1];
        }
        int[] after = new int[nums.length];
        after[nums.length-1] = 1;
        for (int i = nums.length-2; i >=0; i--) {
            after[i] = after[i+1] * nums[i+1];
        }
        int[] res = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            res[i] = pre[i] * after[i];
        }
        return res;
    }
}

7.缺失的第一个正数

考察交换元素
把数字3放到下标为2的数组中
nums[i] = nums[nums[i]-1]

class Solution {
    public int firstMissingPositive(int[] nums) {
        // 3在下标为2的地方
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] > 0 && nums[i] <= nums.length && nums[i] != nums[nums[i]-1]) {
                int temp = nums[nums[i]-1];
                nums[nums[i]-1] = nums[i];
                nums[i] = temp;
            }
        }

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i+1) {
                return i + 1;
            }
        }
        return nums.length+1;
    }
}

8.矩阵置零

考察矩阵
0行和零列需要单独处理

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        boolean rowZero = false;
        boolean colZero = false;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                    // 必须放在这里，否则会受到上述两行的干扰
                    if (i == 0) rowZero = true;
                    if (j == 0) colZero = true;
                }
            }
        }
			// 处理非零行和列
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }

        if (rowZero == true) {
            for (int i = 0; i < n; i++) {
                matrix[0][i] = 0;
            }
        }
        if (colZero == true) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }

    }
}

9.螺旋矩阵

考察矩阵边界
注意结束一次循环就要立马判断

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        List<Integer> res = new ArrayList<>();
        int left = 0, right = n-1, top = 0, bottom = m-1;
        while (true) {
            if (left > right || top > bottom) {
                break;
            }
            for (int i = left; i <= right; i++) {
                res.add(matrix[top][i]);
            }
            if (++top > bottom) break;
            for (int i = top; i <= bottom; i++) {
                res.add(matrix[i][right]);
            }
            if (--right < left) break;
            for (int i = right; i >= left; i--) {
                res.add(matrix[bottom][i]);
            }
            if (--bottom < top) break;
            for (int i = bottom; i >= top; i--) {
                res.add(matrix[i][left]);
            }
            if (++left > right) break;
        }
        return res;
    }
}

10.旋转图像

考察矩阵旋转90°=对角线翻转+中线翻转

class Solution {
    public void rotate(int[][] matrix) {
        // 对角线翻转+中线翻转=顺时针旋转90°
        int m = matrix.length;
        int n = matrix[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < i; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp; 
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n / 2; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][n-j-1];
                matrix[i][n-j-1] = temp;
            }
        }
            
    }
}