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日

相关推荐

  • leetcode54-螺旋矩阵

    原题 给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。 示例 1: 输入: [ [ 1, 2, 3 ], [ 4, 5, 6…

    算法 2019年11月15日
    080
  • leetcode151-翻转字符串里的单词

    原题 给定一个字符串,逐个翻转字符串中的每个单词。 示例 1: 输入: “the sky is blue” 输出: “blue is sky the” 示例 2: 输入: “ he…

    算法 2019年11月22日
    080
  • leetcode162-寻找峰值

    原题 峰值元素是指其值大于左右相邻值的元素。 给定一个输入数组 nums,其中 nums[i] ≠ nums[i+1],找到峰值元素并返回其索引。 数组可能包含多个峰值,在这种情况…

    算法 2020年1月3日
    060
  • leetcode59-螺旋矩阵II

    原题 给定一个正整数 n,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。 示例: 输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, …

    算法 2020年5月13日
    070
  • leetcode198-打家劫舍

    原题 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会…

    算法 2020年5月29日
    050
  • leetcode705-设计哈希集合

    原题 不使用任何内建的哈希表库设计一个哈希集合 具体地说,你的设计应该包含以下的功能 add(value):向哈希集合中插入一个值。 contains(value) :返回哈希集合…

    算法 2019年12月18日
    0140
  • leetcode454-四数相加II

    原题 给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ,使得 A[i] + B[j] + C[k] + D[l] = 0。 为…

    算法 2019年12月27日
    070
  • leetcode152-乘积最大子数组

    原题 给你一个整数数组 nums ,请你找出数组中乘积最大的连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。 示例 1: 输入: [2,3,-2,4] 输出:…

    算法 2020年5月18日
    0110
  • 剑指offer17-打印从1到最大的n位数

    原题(来源Leetcode) 输入数字 n,按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3,则打印出 1、2、3 一直到最大的 3 位数 999。 示例 1: 输入: …

    算法 2020年4月17日
    070
  • leetcode53-最大子序和

    原题 原题 给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4],…

    算法 2020年2月20日
    0120

发表回复

登录后才能评论