【基础算法练习】单调队列与单调栈模板
文章目录
- 单调栈
- 模板题
- 代码模板
- 算法思想
- 单调队列
- 模板题
- 代码模板
- 算法思想
单调栈
模板题
题目链接：ACwing 830. 单调栈
代码模板
#include <iostream>
#include <vector>
#include <stack>using namespace std;const int N = 100010;vector<int> v(N);int main()
{int n;cin >> n;stack<int> st;for (int i = 0; i < n; i++) cin >> v[i];for (int i = 0; i < n; i++) {// v[i] 是当前在遍历的数, v[i] 比栈里的数小就 pop, 直到在栈里找到比他大的数while (!st.empty() && st.top() >= v[i]) st.pop(); if (!st.empty()) cout << st.top() << " ";else cout << -1 << ' ';st.push(v[i]);}return 0;
}
算法思想
单调栈的核心就是根据题目的要求维护一个具有单调性的栈，核心代码：while (!st.empty() && st.top() >= v[i]) st.pop(); 通过这一段代码，在下一个数入栈之前，将不符合题目要求的单调性的栈元素全部出栈，从而做到每次入栈都能保持单调栈的单调性
这就是单调栈的核心的算法思想
单调队列
模板题
题目链接：154. 滑动窗口
代码模板
#include <iostream>
#include <vector>
#include <deque>
using namespace std;const int N = 1000010;vector<int> v(N);deque<int> q;int main()
{int n, k;cin >> n >> k;for (int i = 0; i < n; i++) cin >> v[i];for (int i = 0; i < n; i++) { // 求最小值while (q.size() > 0 && q.back() > v[i]) q.pop_back(); // 比下一个数大的数全部都出队q.push_back(v[i]); // 入队if (i - k >= 0 && q.front() == v[i - k]) q.pop_front(); // 如果这个数在窗口到期了, 就出队if (i >= k - 1) cout << q.front() << " ";}q.clear();cout << endl;for (int i = 0; i < n; i++) { // 求最大值while (q.size() > 0 && q.back() < v[i]) q.pop_back(); // 比下一个数小的数全部都出队q.push_back(v[i]); // 入队if (i - k >= 0 && q.front() == v[i - k]) q.pop_front(); // 如果这个数在窗口到期了, 就出队if (i >= k - 1) cout << q.front() << " ";}return 0;
}
算法思想
单调队列和单调栈的算法思想类似，不过在具体的实现和应用场景上略有不同，单调队列常用于滑动窗口的场景
这里我使用的是双端队列 deque 来模拟（用数组模拟也是一样的），这段：while (q.size() > 0 && q.back() < v[i]) q.pop_back(); 就是维护单调队列单调性的核心代码
除此之外，在滑动窗口的场景下，单调队列还需要维护滑动窗口的大小，以贴合题目的要求