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/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年4月21日
下一篇 2020年4月22日

相关推荐

  • 程序员面试金典08.01-三步问题

    原题(来源Leetcode) 三步问题。有个小孩正在上楼梯,楼梯有n阶台阶,小孩一次可以上1阶、2阶或3阶。实现一种方法,计算小孩有多少种上楼梯的方式。结果可能很大,你需要对结果模…

    算法 2020年6月19日
    04530
  • leetcode837-新21点

    原题 爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏,描述如下: 爱丽丝以 0 分开始,并在她的得分少于 K 分时抽取数字。 抽取时,她从 [1, W] 的范围中随机获得一…

    算法 2020年6月3日
    0110
  • leetcode1115-交替打印FooBar

    原题 我们提供一个类: class FooBar { public void foo() {     for (int i = 0; i < n; i++) {       …

    算法 2020年2月2日
    0170
  • 蓝桥杯试题-小数第n位

    原题 资源限制 时间限制:1.0s 内存限制:256.0MB 问题描述   我们知道,整数做除法时,有时得到有限小数,有时得到无限循环小数。  如果我们把有限小数的末尾加上无限多个…

    算法 2020年2月29日
    080
  • leetcode24-两两交换链表中的节点

    原题 给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。 你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。 示例: 给定 1->2->3->…

    算法 2020年1月20日
    0200
  • leetcode322-零钱兑换

    原题 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。 示例 1…

    算法 2020年3月8日
    0150
  • leetcode210-课程表II

    原题 现在你总共有 n 门课需要选,记为 0 到 n-1。 在选修某些课程之前需要一些先修课程。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们: [0…

    算法 2020年5月17日
    0120
  • leetcode84-柱状图中最大的矩形

    原题 给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。 求在该柱状图中,能够勾勒出来的矩形的最大面积。 以上是柱状图的示例,其中每个柱子的宽…

    2020年1月24日
    0100
  • leetcode167-两数之和II-输入有序数组

    原题 给定一个已按照 升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。 函数应该返回这两个下标值index1和index2,其中index1必须小于index2。 说明…

    算法 2019年11月20日
    0170
  • leetcode56-合并区间

    原题 给出一个区间的集合,请合并所有重叠的区间。 示例 1: 输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]]…

    算法 2020年4月16日
    0160

发表回复

登录后才能评论