单调栈和单调队列

单调栈和单调队列

单调栈和优先队列
单调栈能保证全部元素的单调性，会直接舍去不合的元素，因此没有额外维护成本
小根堆只能保证堆顶是最小值，不会直接舍去元素，但需要O(logn)的decreaseKey成本

有些题目答案一定是当前最大最小值，直接用单调栈维护即可，不是答案直接舍去，时间复杂度为O(n)
当然使用优先队列也正确，因为堆顶一定是极值，但时间复杂度为O(nlogn)

另外，单调队列是双端版的单调栈，元素可以从两端排除，不等于优先队列

  1. 先想暴力怎么做，再考虑把没有用的元素删掉，再看有没有单调性，有单调性的话再看怎么优化
  2. 直接看逆序有没有用，若逆序没用，就有单调性！（在一个从小到大排列的数列中，若左边的数比右边的数大，就称作逆序数）

单调栈

一段本不具有单调性的区间，用一个栈去维护使得其具有单调性（将元素入栈，如果其是逆序的，就让它出栈）

步骤：

  1. while循环判断栈顶元素是否大于 a[i]，如果大于则出栈
  2. 如果此时栈不空则将新的元素 a[i] 赋给答案数组ans
  3. 如果此时栈空则将 -1 赋给答案数组ans
  4. 将当前元素 a[i] 入栈
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
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5+10;
int n,a[N];
int stk[N],tt; //tt为0代表栈空
int ans[N];

int main(){
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    for(int i=0;i<n;i++){
        //这个地方是while
        //直到队列为空或者新的元素小于队尾的元素才进行下一步
        while(tt && stk[tt] >= a[i]) tt--; //出栈
        if(tt) ans[i] = stk[tt];
        else ans[i] = -1;
        stk[++tt] = a[i]; //入栈
    }
    for(int i=0;i<n;i++){
        cout << ans[i] << " ";
    }
    return 0;
}

单调队列

题目链接：滑动窗口

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
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int n,k,a[N];
int q[N],hh=0,tt=-1;
int main(){
    cin >> n >> k;
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    for(int i=0;i<n;i++){
        //判断队头是否已经不在滑动窗口内了
        if(hh <= tt && i-k+1 > q[hh]) hh++;
        while(hh <= tt && a[q[tt]] >= a[i]) tt--; //不满足条件出队
        q[++tt] = i; //新元素入队
        
        //i指针到达滑动窗口末端,可以开始输出队头值
        if(i>=k-1) cout << a[q[hh]] << " "; //输出单调地址队列的队头，即最小值
    }
    cout << "\n";
    
    //队列清空
    hh = 0; tt=-1;
    
    for(int i=0;i<n;i++){
        //判断队头是否已经不在滑动窗口内了
        if(hh <= tt && i-k+1 > q[hh]) hh++;
        //两个for循环只有 这里从 >= 变成了 <=
        while(hh <= tt && a[q[tt]] <= a[i]) tt--; //不满足条件出队
        q[++tt] = i; //新元素入队
        
        //i指针到达滑动窗口末端,可以开始输出队头值
        if(i>=k-1) cout << a[q[hh]] << " "; //输出单调地址队列的队头，即最小值
    }
    return 0;
}

滑动窗口（双端队列）

维护一个固定长度窗口内的最大最小值

tips

  1. 要先判断 //要先判断 q.size() > 0
1
2
3
4
//维护最小值（踢掉目前窗口中 比 要加入窗口值 小的数）
while(q.size() > 0 && a[i] < q.back()){ //要先判断 q.size() > 0
    q.pop_back();
}
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
46
47
48
#include <iostream>
#include <deque>
using namespace std;
const int N = 1e6+10;

int n,k;
int a[N];
// int q[N],hh=0,tt=-1; //队列中元素下标从0开始

int main(){
    cin >> n >> k;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    
    deque<int> q; //双端队列
    //求最小值(构造单调递减队列)
    for(int i=1;i<=n;i++){
        //新元素和队尾元素 循环 比较 （注意这里是while，会一直循环比较）
        while(q.size() && q.back() > a[i]) q.pop_back(); //队尾出队
        q.push_back(a[i]); //新元素入队
        
        //判断目前的队头是否已经滑出了窗口 （这里要取 i-k >= 1）
        
        if(i-k >= 1 && q.front() == a[i-k]){ //如果q.front != a[i-k] 就代表窗口左边界的值早就出队了，不会参与比较了
            q.pop_front();
        }
        //窗口大小满足条件后，开始输出答案
        if(i >= k){
            cout << q.front() << " ";
        }
    }
    
    cout << "\n";
    q.clear();

    //求最大值(构造单调递减队列)
    for(int i = 1; i <= n; i++)
    {
        while(q.size() && q.back() < a[i]) q.pop_back();
        q.push_back(a[i]);
        if(i - k >= 1 && a[i - k] == q.front()) q.pop_front(); 
        if(i >= k) cout << q.front() << " ";

    }
    return 0;
}

滑动窗口的最大值问题

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
#include <deque>
#include <vector>
#include <iostream>

void printMaxInWindows(const std::vector<int>& nums, int windowSize) {
    std::deque<int> window;
    for (int i = 0; i < nums.size(); ++i) {
        // 移除窗口外的元素
        while (!window.empty() && window.front() <= i - windowSize) { //window.front() <= i - windowSize 符合这个条件才代表窗口的左边界还在队列中
            window.pop_front();
        }
        // 移除小于当前元素的元素
        while (!window.empty() && nums[window.back()] < nums[i]) {
            window.pop_back();
        }
        window.push_back(i);
        // 输出窗口内的最大值
        if (i >= windowSize - 1) {
            std::cout << nums[window.front()] << " ";
        }
    }
}

int main() {
    std::vector<int> nums = {4, 3, 5, 4, 3, 3, 6, 7};
    int windowSize = 3;
    printMaxInWindows(nums, windowSize);
    return 0;
}


完美区间

给出一个长度为N(1 ≤ N ≤ 50000)的数字队列，定义完美区间为数字队列中连续的一段，并且其中最大与最小数字之差不得超过M(1 ≤ M ≤ 50000)。

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
46
47
48
49
50
51
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

int countPerfectIntervals(vector<int>& nums, int M) {
    int n = nums.size();
    int count = 0;
    deque<int> minDeque; // 用于存储最小值索引的双端队列
    deque<int> maxDeque; // 用于存储最大值索引的双端队列

    for (int i = 0; i < n; ++i) {
        // 维护最小值队列
        while (!minDeque.empty() && nums[i] < nums[minDeque.back()]) {
            minDeque.pop_back();
        }
        minDeque.push_back(i);

        // 维护最大值队列
        while (!maxDeque.empty() && nums[i] > nums[maxDeque.back()]) {
            maxDeque.pop_back();
        }
        maxDeque.push_back(i);

        // 当窗口大小超过n时，移动窗口
        while (nums[i] - nums[minDeque.front()] > M) {
            if (minDeque.front() == i - minDeque.size() + 1) {
                minDeque.pop_front();
            }
        }
        while (nums[maxDeque.front()] - nums[i] > M) {
            if (maxDeque.front() == i - maxDeque.size() + 1) {
                maxDeque.pop_front();
            }
        }

        // 计算完美区间的数量
        count += (i - minDeque.front() + 1);
    }

    return count;
}

int main() {
    vector<int> nums = {1, 5, 3, 9, 2, 8, 7, 4, 6};
    int M = 3;
    cout << "Number of perfect intervals: " << countPerfectIntervals(nums, M) << endl;
    return 0;
}

每个字母恰好出现两次的最长子串

给一个只包含小写字母且长度不超过100000的字符串，找出每个字母恰好出现两次的最长子串。

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
#include <iostream>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;

string longestSubstringWithEqualFrequency(string s) {
    int n = s.length();
    unordered_map<char, int> count;
    int maxLen = 0;
    int left = 0;
    string result;

    for (int right = 0; right < n; ++right) {
        char c = s[right];
        count[c]++;
        
        // 检查当前窗口是否有效
        while (count[c] > 2) {
            char leftChar = s[left];
            count[leftChar]--;
            left++;
        }

        // 检查当前窗口是否包含所有字符恰好两次
        if (all_of(count.begin(), count.end(), [](const pair<char, int>& p) { return p.second == 2; })) {
            if (right - left + 1 > maxLen) {
                maxLen = right - left + 1;
                result = s.substr(left, maxLen);
            }
        }
    }

    return result;
}

int main() {
    string s = "aabbcc";
    cout << "Longest substring with equal frequency: " << longestSubstringWithEqualFrequency(s) << endl;
    return 0;
}

算法 > 数据结构
#算法 #数据结构
单调栈和单调队列
https://cs-lb.github.io/2024/04/11/数据结构/单调栈和单调队列/
作者
Liu Bo
发布于
2024年4月11日
许可协议