题目列表

239. 滑动窗口最大值

具体实现

239. 滑动窗口最大值

  • 只要一个队列中，右边的大于等于左边的数，那么左边的数就没有意义，就可以把左边的数删除掉
  • 双端队列-单调队列
    1. class Solution {
    2.   public int[] maxSlidingWindow(int[] nums, int k) {
    3.       //一共有多少结果
    4.       int n = nums.length;
    5.       int[] res = new int[n - k + 1];
    6.       Deque<Integer> q = new ArrayDeque<>();
    7.       //双端队列-单调队列
    8.       for(int i = 0, t = 0; i < n; i++){
    9.           //右端点为i,则左端点为i - k + 1
    10.           //如果左端点比队列中首元素还要大的话，证明首元素已经滑出窗口了
    11.           if(!q.isEmpty() && i - k + 1 > q.peekFirst()) q.removeFirst();
    12.           //把小于nums[i]的优化掉
    13.           while(!q.isEmpty() && nums[i] > nums[q.peekLast()]) q.removeLast();
    14.           q.addLast(i);
    15.           //i从k-1的位置开始才输出队列最大值
    16.           if(i >= k - 1) res[t++] = nums[q.peekFirst()];
    17.       }
    18.       return res;
    19.   }
    20. }