单调栈：给定一个序列，在这个序列中对每一个数，求出这个数左边比这个数小的且离这个数最近的数在什么地方，或者说是什么
e.g.
对于数列
3 4 2 6 5
返回
-1 3 -1 2 2暴力朴素做法
for (int i = 0; i < n; i ++ )
{
for (int j = i - 1; j >= 0; j -- )
{
if (a[i] > a[j])
{
cout << a[j] << '\n';
break;
}
}
}可以发现，在 i 往右走的过程中，可以用栈存储 i 左边的所有元素。然而有些元素永远不会作为答案被输出。只要有逆序的关系，前面的数一定会被删掉。所以我们可以保证栈里的元素一定是单调的。
假设我们现在已经完成了一个单调上升的栈，那么当遇到新元素时，如果新元素比栈顶更小，那么假设原来会输出栈顶，则现在栈顶不会输出栈顶，转而输出更小的新元素。所以我们可以一直弹出栈顶，直到栈顶小于新元素为止，此时插入新元素。这也是单调栈更新的办法。
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int n; cin >> n;
stack<int> stk;
for (int i = 0; i < n; i ++)
{
int x; cin >> x;
while (!stk.empty() && stk.top() >= x) stk.pop();
if (!stk.empty()) cout << stk.top() << ' ';
else cout << -1 << ' ';
stk.push(x);
}
return 0;
}代码如上
我们发现代码发现每个元素最多进栈一次，出栈一次，一共2n次操作，时间复杂度为O(n)
评论（0）
暂无评论