题目

image.png

思路

  • 维护窗口，向右移动时左侧超出窗口的值弹出，因为需要的是窗口内的最大值，所以只要保证窗口内的值是递减的即可，小于新加入的值全部弹出。最左端即为窗口最大值

    代码

    1.   public int[] maxSlidingWindow(int[] nums, int k) {
    2.       if (nums.length <= 1 || k == 1) return nums;
    3.       LinkedList<Integer> queue = new LinkedList<>();
    4.       int[] res = new int[nums.length - k + 1];
    5.       for (int i = 0; i < nums.length; i++) {
    6.           while (!queue.isEmpty() && nums[queue.getLast()] <= nums[i]) {
    7.               queue.removeLast();
    8.           }
    9.           queue.addLast(i);
    10.           if (queue.peek() <= i - k) {
    11.               queue.removeFirst();
    12.           }
    13.           if (i - k + 1 >= 0) {
    14.               res[i - k + 1] = nums[queue.peek()];
    15.           }
    16.       }
    17.       return res;
    18.   }
    滑动窗口最大值