概述
栈中元素满足单调性的线性数据结构
板子题
题意
即求每一个数的下一个更大数的下标。
思路
- 维护一个单调递减的栈。
- 每次插入元素与栈顶进行比较
- 大于等于栈顶
- 栈顶不停出栈，直到该元素小于栈顶或栈为空。
- 出栈的每一个栈顶，对应的答案都是该元素。
- 小于栈顶
- 入栈
- 大于等于栈顶
时间复杂度
从出栈入栈的角度切入分析，所有元素都只会出栈一次，入栈一次，所以复杂度就是 \(\operatorname O(n)\)
代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n + 1);
stack<int> st;
vector<int> ans(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
while(!st.empty() && a[i] > a[st.top()]) {
ans[st.top()] = i;
st.pop();
}
st.push(i);
}
while(!st.empty()) {
ans[st.top()] = 0;
st.pop();
}
for (int i = 1; i <= n; i++) {
cout << ans[i] << ' ';
}
cout << endl;
return 0;
}
最大矩形面积
D-Largest Rectangle in a Histogram_0x11 基本数据结构-栈 (nowcoder.com)
思路
考虑维护每一个元素 \(i\) 左端第一个比它小的下标 \(l_i\) 及右端第一个比它小的下标 \(r_i\)。
显然可能的面积就是 \(a_i \times (r_i - l_i - 1)\)
代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
while(cin >> n && n) {
vector<int> a(n + 2);
vector<int> l(n + 2), r(n + 2);
for (int i = 1; i <= n; i++) cin >> a[i];
a[n + 1] = 0;
long long ans = 0;
stack<int> st;
for (int i = 1; i <= n; i++) {
while(!st.empty() && a[i] <= a[st.top()]) {
st.pop();
}
if (!st.empty()) l[i] = st.top();
else l[i] = 0;
st.push(i);
}
while(!st.empty()) st.pop();
for (int i = n; i; i--) {
while(!st.empty() && a[i] <= a[st.top()]) {
st.pop();
}
if (!st.empty()) r[i] = st.top();
else r[i] = n + 1;
st.push(i);
}
for (int i = 1; i <= n; i++) {
ans = max(ans, 1LL * a[i] * (r[i] - l[i] - 1));
}
cout << ans << endl;
}
return 0;
}
CF1730C
题意
给定一个仅包含 \(0\) 到 \(9\) 这几个数字的字符串，你可以执行以下操作任意次：
选择字符串中的一个数字 \(d\)，将 \(d\) 删除后，向字符串任意位置插入一个数字 \(\min(d+1,9)\)
求能够得到的字典序最小的字符串。
思路
想要让字典序最小，就要尽可能将小的数放在前面。每次执行一次操作后，我们都会让一个数变大，只有变大后把它放在字符串后面，让一个更小的数能到前面来，他才能更优。
维护一个单调栈，将弹出的元素 \(d=\min(d+1,9)\) 全部存入一个 vector 中，将所有元素排序。最后输出答案，在输出单调栈中元素的同时，输出 vector 中与之相等的元素，因为已经排完序了，直接从前向后扫即可。
void solve() {
string s;
stack<char> st;
vector<char> els,ans;
cin >> s;
int len = s.length();
for(int i = 0;i < len;i++) {
while(!st.empty() && st.top() > s[i]) {
els.push_back(min((char)(st.top() + 1),'9'));
st.pop();
}
st.push(s[i]);
}
while(!st.empty()) {
ans.push_back(st.top());
st.pop();
}
sort(els.begin(),els.end());
int pos = 0;
for(int i = ans.size() - 1;i >= 0;i--) {
cout << ans[i];
while(pos < els.size() && els[pos] >= ans[i]
&& els[pos] <= ans[i-1] && i > 0) cout << els[pos++];
}
for(int i = pos;i < els.size();i++) cout << els[i];
cout << endl;
return;
}