单调栈
题目描述
给出项数为
定义函数
试求出
Solution
这个基础算法经常困住我,必须解决掉
倒着遍历:
void solve() {
int n;cin >> n;
vector<int> a(n + 1), f(n + 1);
for (int i = 1;i <= n;i++)cin >> a[i];
vector<int> stk;
for (int i = n;i >= 1;i--) {
while (stk.size() && a[i] >= a[stk.back()]) stk.pop_back();
if (stk.size())f[i] = stk.back();
stk.push_back(i);
}
for (int i = 1;i <= n;i++)cout << f[i] << " ";
}
正着遍历:
void solve() {
int n;cin >> n;
vector<int> a(n + 1), f(n + 1);
for (int i = 1;i <= n;i++)cin >> a[i];
vector<int> stk;
for (int i = 1;i <= n;i++) {
while (stk.size() && a[i] > a[stk.back()])f[stk.back()] = i, stk.pop_back();
stk.push_back(i);
}
for (int i = 1;i <= n;i++)cout << f[i] << " ";
}