239. 滑动窗口最大值

教程

【C15【模板】单调队列 滑动窗口最值】 https://www.bilibili.com/video/BV1H5411j7o6/?share_source=copy_web&vd_source=82180e49f17daecf14bb6f246fc29cd0

【单调队列 滑动窗口最大值【基础算法精讲 27】】 https://www.bilibili.com/video/BV1bM411X72E/?share_source=copy_web&vd_source=82180e49f17daecf14bb6f246fc29cd0

【单调队列正式登场！| LeetCode：239. 滑动窗口最大值】 https://www.bilibili.com/video/BV1XS4y1p7qj/?share_source=copy_web&vd_source=82180e49f17daecf14bb6f246fc29cd0

用队列模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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++) {
            //入
            while (!q.empty() && nums[q.back()] <= nums[i])
                q.pop_back();
            q.push_back(i);
            //出
            if (i - q.front() >= k)
                q.pop_front();
            //记录答案
            if (i >= k - 1)
                ans.push_back(nums[q.front()]);
        }
        return ans;
    }
};

https://leetcode.cn/problems/sliding-window-maximum/solutions/2777540/239-hua-dong-chuang-kou-zui-da-zhi-by-jo-fud8

代码

测试用例

测试结果

测试结果

347. 前 K 个高频元素

https://leetcode.cn/problems/top-k-frequent-elements/solutions/2784499/347-qian-k-ge-gao-pin-yuan-su-by-joker-e-mlnb

栈与队列总结

见卡哥代码随仙录

https://programmercarl.com/%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E6%80%BB%E7%BB%93.html#%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E7%9A%84%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80