一、题目：

AcWing 830. 单调栈 - AcWing

暴力算法思想 

双指针算法，本质上是比较操作，两个循环，时间复杂度高。通过栈可以一次遍历。

可以知道，只要前面有一个小于我的数，就可以。如果前面的数，都比我前面的大，都不用比前面的了，只要前面的不行，其他的也肯定不行。所以只要前面的大于后面的，就把前面的pop掉。

单调栈思想：

借助栈来实现，题目说要前面一个比自己小的。

如果我入栈为空，那么就输出-1

如果我入栈非空，那么就看栈顶是否＜我，如果比我大于等于，那么我就pop他，直至为空或者知道找到一个小于我的。

代码（练习stl)

多用了一个vector动态数组有点浪费。

#include<bits/stdc++.h>
using namespace std;stack<int>stk;
vector<int> a;int main() {int n;cin >> n;for(int i = 0; i < n; i ++) {int x; cin >> x;a.push_back(x);}int i = 0;while(i < a.size()) {if(stk.empty()) {stk.push(a[i++]);cout << -1 << " ";}while(!stk.empty() && stk.top()>=a[i]) {stk.pop();}if(stk.empty()) cout << -1 << " ";else if(!stk.empty()) cout << stk.top() << " ";stk.push(a[i++]);}return 0;
}

代码2（数组实现）

#include<bits/stdc++.h>
using namespace std;const int N = 1e5+10;int a[N], top = 0;
int n;int main() {cin >> n;for(int i = 0; i < n; i ++) {int x;cin >> x;while(top && a[top-1]>=x) top --;if(top) cout << a[top-1] << " ";else cout << -1 << " ";a[top++] = x;}return 0;
}

代码3（练习stl）

#include<bits/stdc++.h>
using namespace std;stack<int> stk;int n;int main() {cin >> n;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;
}