首页 算法 单调队列

# 单调队列

# 算法原理

  1. 单调队列只允许从队尾加入元素
  2. 单调队列可以从队尾和队头弹出元素
  3. 单调队列每次进入元素时会把小于 / 大于它的元素从队尾弹出

# 算法性质

  1. 保证了队列中必然是有序递减 / 递增的
  2. 队头必然是最大 / 最小的元素
  3. 相对有序性，即元素在队列中的顺序和实际的 相对顺序 一致

但是要注意的其实还以几个，那就是 比如滑动窗口中，如果窗口过了，那么只需要判断队头元素是否等于弹出的值，等于弹出即可 入队元素如果比队头小 / 大，满足递减 / 递增性，是不会被弹出的

# 应用

如滑动窗口问题，比如找滑动窗口内的最大值，滑动窗口每次会添加一个新值，然后把最后一个元素弹出。 最简单的方式是对每次得到的新的区间进行最大值的检索。 其实可以使用单调队列来模拟 最后一个最大值的位置 ，即队头就是最大值的位置，且其他元素会保持相对的位置 那么为什么单调队列能保证正确性呢？其中一个最重要的性质就是，单调队列可以保证 最后一个最大值 的位置 如果最大值是区间的最后一个值，那么它仍然是下一个区间的可能最大值
如果最大值是上一个区间的第一个值，那么它之后会跟着其他的次大值 / 次次大值，且相对位置不变. 通俗的话来说，优先队列可以找到距离当前点最高 / 低的向左侧的阶梯

# 实现

c++ 里有 deque, 可以用作双端队列

# A. 滑动窗口

https://leetcode.cn/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/submissions/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        deque<int> q;
        for(int i=0;i<k;++i){
            while(!q.empty() && nums[i]>=nums[q.back()]){
                q.pop_back();
            }
            q.push_back(i);
        }

        vector<int> ans = {nums[q.front()]};
        for(int i = k;i<n;++i){
            while(!q.empty() && nums[i] >= nums[q.back()]){
                q.pop_back();
            }
            q.push_back(i);
            while(q.front()<=i-k){
                q.pop_front();
            }
            ans.push_back(nums[q.front()]);
        }
        return ans;
    }
};

# B. 接雨水

根据上面的说法，我们可以将题目改写为 某个点上最多可以存放的雨水数量

这样一来，我们就只需要找到距离该点向右和向左的最高的阶梯即可 https://leetcode.cn/problems/trapping-rain-water/submissions/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int leftMax[n],rightMax[n];

        deque<int> maxQue;
        maxQue.push_back(0);
        leftMax[0] = -1;
        rightMax[0] = -1;
        for(int i=1;i<height.size();++i){
            while(!maxQue.empty() && height[i]>=height[maxQue.back()]){
                maxQue.pop_back();
            }
            maxQue.push_back(i);
            if(maxQue.front()!=i){
                leftMax[i] = maxQue.front();
            }else{
                leftMax[i] = -1;
            }
        }

        maxQue.clear();
        maxQue.push_back(n-1);
        for(int i=height.size()-1;i>=0;--i){
            while(!maxQue.empty() && height[i]>=height[maxQue.back()]){
                maxQue.pop_back();
            }
            maxQue.push_back(i);
            if(maxQue.front()!=i){
                rightMax[i] = maxQue.front();
            }else{
                rightMax[i] = -1;
            }
        }

        int ans = 0;
        for(int i=1;i<height.size();++i){
            if(leftMax[i]!=-1 && rightMax[i] != -1){
                ans += (min(height[leftMax[i]],height[rightMax[i]]) - height[i]);
            }
        }
        return ans;
    }
};