开发者社区> 游客z3jcatjk57fiu> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

每日算法系列【LeetCode 239】滑动窗口最大值

简介: 给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回滑动窗口中的最大值。
+关注继续查看

题目描述


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

提示你可以假设 k 总是有效的,在输入数组不为空的情况下,1 ≤ k ≤ 输入数组的大小。

题解


双端单调队列


本题要找长度为 k 的区间的最大值。模拟这个区间的移动过程,可以发现,右边增加一个数,左边必然会去掉一个数。

那么最大的数有什么性质呢?可以发现,如果扫描区间末尾,在已经遍历过的数之中,一个数 a 在 b 前面,并且 a 还比 b 小,那么 a 在之后的区间里永远无法成为最大值。

所以我们遍历到一个数时,它之前的所有比它小的数都可以去掉了,只保留比它大的数就行了。这就让人想到了之前介绍过的单调栈,但是本题中是先进先出,所以要改用单调队列。此外队列末尾不仅要增加元素,还得维护单调递减,适当去除一些元素,所以队列两端都得有插入和删除的功能。所以本题要使用双端队列,而队列中的元素又是单调递减的,所以又是双端单调队列。

这样思路就很明确了:

  • 遍历元素 nums[i] ,然后跟队列尾部元素比较,如果比尾部元素大,就出队,然后继续比较,直到 nums[i] 小于尾部元素,然后将它入队。
  • 然后用一下队列首部元素的下标,计算出队列中区间的长度,如果大于 k 了,那么队首元素就要出队。
  • 最后队首元素就是当前区间的最大值。

分块法


试想如果我们将数组划分为相同大小的若干块,每一块中最大值都是知道的话,那么要求区间最大值,只需要看它在哪几块里就行了。

那么块的大小应该设成多少呢?

如果块大小为 k ,就可以发现长度为 k 的区间 [i, j] 要么正好就是一个完整的块,要么跨越了两个相邻块。那么我们只需要知道 i 到它那块末尾元素中最大值,以及 j 到它那块开头最大值就行了,两个部分合并求最大值就是区间的最大值了。而每个元素到它自己那块的开头和末尾的最大值都可以预处理出来,方法和求前缀和类似。

那为什么块大小不能是其他值呢?如果块大小大于 k ,那么会出现区间完全包含于一块之中的情况,那就和不分块一样了。如果块大小小于 k ,那么就会出现区间横跨了好几块,那么还得遍历中间块的最大值。极端情况下如果块大小为 1 ,那么就等于暴力求解。

代码


双端单调队列(c++)



class Solution {
    public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k){ 
        int n = nums.size(); 
        deque<int> Q; 
        vector<int> res; 
        for (int i = 0; i < n; ++i) { 
            while (!Q.empty() && nums[i] >= nums[Q.back()])
                Q.pop_back(); 
            Q.push_back(i);
            if (i - Q.front() + 1 > k) Q.pop_front();
            if (i >= k-1) res.push_back(nums[Q.front()]);
        }        return res;
    }
};

双端单调队列+数组实现(c++)



class Solution {
    public:
    
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> Q(n, 0);
        vector<int> res;
        int l = 0, r = 0; 
        for (int i = 0; i < n; ++i) { 
            while (r-l > 0 && nums[i] >= nums[Q[r-1]]) r--;
            Q[r++] = i;  
            if (i - Q[l] + 1 > k) l++; 
            if (i >= k-1) res.push_back(nums[Q[l]]);
        } 
        return res; 
    }
};

分块法(c++)


class Solution {
    public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> lmax(n, 0), rmax(n, 0);
        vector<int> res;
        if (!n) return res;
        for (int i = 0; i < n; ++i) { 
            if (i%k == 0) lmax[i] = nums[i];
            else lmax[i] = max(lmax[i-1], nums[i]);
        }
        for (int i = n-1; i >= 0; --i) { 
           if ((i+1)%k|| i == n-1) rmax[i] = nums[i];            else rmax[i] = max(rmax[i+1], nums[i]);
        } 
        for (int i = k-1; i < n; ++i) {
            res.push_back(max(lmax[i], rmax[i-k+1]));
        } 
        return res;
    }
};

双端单调队列(python)


import collections
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        Q = collections.deque() 
        res = [] 
        for i in range(n):
            while len(Q) > 0 and nums[i] >= nums[Q[-1]]:               
                Q.pop() 
                Q.append(i)  
                if i - Q[0] + 1 > k:
                    Q.popleft() 
                    if i >= k-1:               
                        res.append(nums[Q[0]])
                        return res

双端单调队列+数组实现(python)

import collections
class Solution: 
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: 
        n = len(nums) 
        Q = [0] * n 
        res = [] 
        l, r = 0, 0 
        for i in range(n):
            while r-l > 0 and nums[i] >= nums[Q[r-1]]:
                r -= 1
                Q[r] = i 
                r += 1 
                if i - Q[l] + 1 > k: 
                    l += 1 
                    if i >= k-1: 
                        res.append(nums[Q[l]])
                        return res

分块法(python)



import collections
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: 
        n = len(nums) 
        lmax, rmax = [0] * n, [0] * n
        res = []
        if n == 0: 
            return res 
        for i in range(n):
            if i%k == 0: 
                lmax[i] = nums[i] 
                else:
                    lmax[i] = max(lmax[i-1], nums[i])
                    for i in range(n-1, -1, -1): 
                        if (i+1)%k == 0 or i == n-1: 
                            rmax[i] = nums[i] 
                            else:  
                                rmax[i] = max(rmax[i+1], nums[i])        
                                for i in range(k-1, n):            
                                    res.append(max(lmax[i], rm)        return res
                                              

后记


双端队列在 c++ 和 python 中都有 deque 的实现,如果你不会用的话,也可以用一个数组自己模拟一下,我觉得反而更加方便一点。

image.png

作者简介:godweiyang知乎同名华东师范大学计算机系硕士在读,方向自然语言处理与深度学习喜欢与人分享技术与知识,期待与你的进一步交流~

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
LeetCode 6-10 题 详解 Java版 ( 万字 图文详解 LeetCode 算法题6-10 =====>>> <建议收藏>)
LeetCode 6-10 题 详解 Java版 ( 万字 图文详解 LeetCode 算法题6-10 =====>>> <建议收藏>)
12 0
「LeetCode」JavaScript-插入排序⚡️
「LeetCode」JavaScript-插入排序⚡️
17 0
「LeetCode」JavaScript-顺序搜索⚡️
「LeetCode」JavaScript-顺序搜索⚡️
31 0
「LeetCode」JavaScript-归并排序⚡️
「LeetCode」JavaScript-归并排序⚡️
20 0
「LeetCode」JavaScript-归并排序⚡️
「LeetCode」JavaScript-归并排序⚡️
22 0
辗转相除法_欧几里得算法_java的实现(求最大公约数)
辗转相除法_欧几里得算法_java的实现(求最大公约数)
28 0
好程序员web前端分享javascript枚举算法
好程序员web前端分享javascript枚举算法,题目:在1,2,3,4,5 五个数中,我们随机选取 3个数。问有多少种取法?并且把每种取出数的方法列举出来。 乍看这道题,其实感觉没什么难度。三个for循环不就解决问题了。
1023 0
辗转相除法_欧几里得算法_java的实现(求最大公约数)
辗转相除法,又被称为欧几里德(Euclidean)算法, 是求最大公约数的算法。 当然也可以求最小公倍数。 算法描述   两个数a,b的最大公约数记为GCD(a,b)。a,b的最大公约数是两个数的公共素因子的乘积。
1523 0
217
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载