单调队列

目录

一，单调队列

二，模板实现

三，OJ实战

剑指 Offer 59 - I. 滑动窗口的最大值

---

一，单调队列

单调队列是双端队列的拓展，支持尾部插入，双端删除，其中的数据始终维持单调性，从而队首就是所需的最值信息。

和单调栈类似，单调队列用于处理一个数组，扫描数组时，依次尾部插入一个数。

尾部插入过程中，为了维持单调性，可能需要先执行尾部删除（对应强制单调栈）。

而队首的删除操作，由外部决定调用时机。

二，模板实现

//单调队列
class MonotonicQueue {
public:MonotonicQueue(int type) { //0递增队列，队首最小，1递减队列，队首最大this->type = type;id = 0;}void push_back(int x) {while (!q.empty() && (type ? (m[q.back()] < x) : (m[q.back()] > x)))q.pop_back();q.push_back(id);m[id++] = x;}void pop_front() {if (!q.empty())q.pop_front();}void pop_back() {if (!q.empty())q.pop_back();}int frontId() {return q.front();}int front() {return m[q.front()];}int tailId() {return q.back();}int size() {return q.size();}
private:deque<int>q;map<int, int>m;int type, id;
};

三，OJ实战

剑指 Offer 59 - I. 滑动窗口的最大值

题目：

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

进阶：

你能在线性时间复杂度内解决此题吗？

示例:

输入: 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

 思路一：

线段树

class SegmentTree<2> opt;class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {int n = nums.size();for (int i = 0; i < n; i++)*(opt.getData() + i + 1) = nums[i];opt.build(n);vector<int>ans;ans.resize(n - k + 1);for (int i = 0; i < ans.size(); i++)ans[i] = opt.query(i + 1, i + k);return ans;}
};

思路二：

单调队列

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int>ans;MonotonicQueue q(1);for (int i = 0; i < k; i++)q.push_back(nums[i]);for (int i = k; i < nums.size(); i++) {ans.push_back(q.front());q.push_back(nums[i]);if (q.tailId() - k == q.frontId())q.pop_front();}ans.push_back(q.front());return ans;}
};