239. 滑动窗口最大值_面试题59 - I. 滑动窗口的最大值

问题

例子

思路

• 方法1 暴力
  $$

  $$

• 方法2
  暴力法O(n^2)，怎么降到O(n)？，容器保存窗口中的值，如果能获取最大呢？让最大的值处于peek，可采用保存递减值的方式。每次移动窗口后，要把容器中的非窗口的值去掉，通过下标，所以用容器保存下标，所以考虑使用双端队列

  双向队列【因为要在两端进行操作】保存下标【为了可以排除非窗口的元素】：其中下标对应的值呈递减，其下标呈现递增
  队列只保留当前滑动窗口中有的元素的索引。第一个保存窗口内的最大值。队列保存该窗口内的递减，且对于重复的元素，保存靠近右边界的那个。

移除比当前元素小的所有元素，然后把它放进入尾部。即队列的顶部是当前窗口的最大值的下标

代码

//方法1
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length==0) return new int[0];
        int[] res = new int[nums.length-k+1];
        for(int i=0; i+k-1<nums.length; i++) {
            int max = nums[i];
            for(int j=1; j<k; j++) {
                max = Math.max(max, nums[i+j]);
            }
            res[i]=max;
        }
        return res;
    }
}
//方法2
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length==0) return new int[0];
        Deque<Integer> q = new LinkedList<>();
        int[] res = new int[nums.length-k+1];
        for(int i=0; i<nums.length; i++) {
       		//如果下标不在以i为结尾的窗口中
            while(q.size()>0 && q.peekFirst()<=i-k)
                q.pollFirst();
            while(q.size()>0 && nums[i]>=nums[q.peekLast()])
                q.pollLast();
            q.offerLast(i);
            if(i>=k-1) res[i-k+1]=nums[q.peekFirst()];
        }
        
        return res;