滑动窗口最大值(leetcode hot100)

简介: 滑动窗口最大值(leetcode hot100)

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

示例 2:


输入:nums = [1], k = 1

输出:[1]

有两种思路,第一种最容易想到的,我们可以想到一种非常合适的数据结构,那就是优先队列(堆),其中的大根堆可以帮助我们实时维护一系列元素中的最大值。(代码注释写的非常详细)

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res; // 存储滑动窗口的最大值
        priority_queue<pair<int,int>> pp; // 优先队列,存储元素值和对应的索引
        // 初始化优先队列,将前 k 个元素加入队列
        for(int i = 0; i < k; i++)
            pp.emplace(nums[i], i); // 将元素值和索引对加入队列
        res.push_back(pp.top().first); // 将滑动窗口的最大值加入结果数组
        // 从第 k 个元素开始遍历
        for(int i = k; i < nums.size(); i++)
        {
            pp.emplace(nums[i], i); // 将新元素加入队列
            // 移除滑动窗口外的元素
            while(pp.top().second <= i - k) 
                pp.pop(); // 弹出队列头部小于等于 i - k 的元素
            res.push_back(pp.top().first); // 将当前滑动窗口的最大值加入结果数组
        }
        return res; // 返回滑动窗口的最大值数组
    }
};

第二种写法,更加高级,单调栈,双端队列不熟悉的先复习一下。

单调队列套路(代码注释写的非常详细)

  • 入(元素进入队尾,同时维护队列单调性)
  • 出(元素离开队首)
  • 记录/维护答案(根据队首)

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ans;
        deque<int> q; // 双端队列
        for (int i = 0; i < nums.size(); i++) {
            // 1. 入
            while (!q.empty() && nums[q.back()] <= nums[i]) {
                q.pop_back(); // 维护 q 的单调性
            }
            q.push_back(i); // 入队
            // 2. 出
            if (i - q.front() >= k) { // 队首已经离开窗口了
                q.pop_front();
            }
            // 3. 记录答案
            if (i >= k - 1) {
                // 由于队首到队尾单调递减,所以窗口最大值就是队首
                ans.push_back(nums[q.front()]);
            }
        }
        return ans;
    }
};
相关文章
|
28天前
【LeetCode 26】239.滑动窗口最大值
【LeetCode 26】239.滑动窗口最大值
29 1
|
29天前
【LeetCode 04】滑动窗口法总结
【LeetCode 04】滑动窗口法总结
15 0
|
3月前
|
存储 Python
【Leetcode刷题Python】239. 滑动窗口最大值
文章介绍了两种解决LeetCode上"滑动窗口最大值"问题的方法:使用大堆树和双向递减队列,提供了详细的解析和Python代码实现。
30 0
|
5月前
|
算法 搜索推荐
力扣每日一题 6/15 滑动窗口
力扣每日一题 6/15 滑动窗口
30 1
|
5月前
|
算法
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
|
4月前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
5月前
|
算法 索引
力扣随机一题 位运算/滑动窗口/数组
力扣随机一题 位运算/滑动窗口/数组
40 0
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
54 6
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
106 2