原题

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

进阶：

你能在线性时间复杂度内解决此题吗？

示例 1：

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7] 
解释: 

  滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

提示：

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length

解法

思想

使用一个双端队列维护一个单调递减队列（但实际上存放的是数组的下标），每滑动一次窗口，如果进来的元素比队尾下标对应的元素小，则进入队尾，否则将队列尾比该元素小的元素都弹出（类似单调栈的思想），再进入队尾，那么任意时刻队首元素即为当前最大元素的下标，而如果滑动窗口后队首元素的下标等于当前下标-k，说明队首元素过期，应该从队列首部弹出。

代码

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> qmax = new LinkedList<>();
        int[] ans = new int[nums.length-k+1];
        int index = 0;
        for(int i = 0;i<nums.length;i++){
            while(!qmax.isEmpty()&&nums[qmax.peekLast()]<=nums[i]){
                qmax.pollLast();
            }
            qmax.addLast(i);
            if(qmax.peekFirst()==i-k){
                qmax.pollFirst();
            }
            if(i>=k-1){
                ans[index++] = nums[qmax.peekFirst()];
            }
        }
        return ans;
    }
}

下面这种方法的思想是记录当前窗口内最大元素的下标，如果滑出去了重新选举最大值，如果没滑出去将进来的元素与当前最大元素比较。它和暴力又不太一样，因为其实重新选举的次数较少，实际leetcode中这种方法反而更快，可能是因为数据量的原因：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums == null || nums.length == 0 || k < 1)return new int[0];
        if(k == 1)return nums;
        int[] maxes = new int[nums.length - k + 1];
        int maxIdx = 0;
        //求出前k个元素的最大值索引
        for(int i = 1; i < k; i++){
            if(nums[i] > nums[maxIdx])maxIdx = i;
        }
        //li是滑动窗口的最左端
        for(int li = 0; li < maxes.length; li++){
            //ri是滑动窗口的最右端的索引
            int ri = li + k- 1;
            if(maxIdx < li){//最大值的索引不在滑动窗口范围内
                maxIdx = li;
                //求出[li, ri]范围内最大值的索引
                for(int i = li + 1; i <= ri; i++){
                    if(nums[i] > nums[maxIdx])maxIdx = i;
                }
            }else if(nums[ri] >= nums[maxIdx]){//最大值的索引在滑动窗口的范围内，并且大于最大值
                maxIdx = ri;
            }
            maxes[li] = nums[maxIdx];
        }
        return maxes;
    }
}

原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode239-%e6%bb%91%e5%8a%a8%e7%aa%97%e5%8f%a3%e6%9c%80%e5%a4%a7%e5%80%bc/

leetcode239-滑动窗口最大值

原题

解法

思想

代码

相关推荐

发表回复