leetcode239-滑动窗口最大值

原题

给定一个数组 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/

发表评论

电子邮件地址不会被公开。