[AcWing]830. 单调栈（C++实现）单调栈模板题

• 1. 题目
• 2. 读题（需要重点注意的东西）
• 3. 解法
• 4. 可能有帮助的前置习题
• 5. 所用到的数据结构与算法思想
• 6. 总结

单调栈的用处：找当前节点左边比它小的第一个节点（也可相应为找右边比它大的第一个节点等等）
思路：将栈置空，当每个节点入栈时，判断栈顶元素和该元素的大小，如果当前元素小于栈顶元素，则将栈顶元素出栈，再逐一比较，直到遇到小于当前元素的栈顶元素，或者将栈置空。最后将该元素输入该栈。

如 2 3 1 5 4，找当前节点左边比它小的第一个节点，若没有，输出-1.

2入栈，栈内元素为 2，输出 -1；
3与2比较，3大于2，直接入栈，栈内元素为 2 3。输出2；
1与2比较，3出栈，2出栈，1入栈，栈内元素为1。输出-1；
5与1比较，直接入栈，栈内元素为1 5。输出1；
4与5比较，5出栈，4入栈，栈内元素为 1 4；输出1。
最终输出为 -1 2 -1 1 1。

---------------------------------------------------解法---------------------------------------------------

#include
using namespace std;

const int N = 1e5+10;
int q[N],hh,tt = -1;
int main(){
    int m;
    cin >> m;
    while(m--){
        string op;
        cin >> op;
        if(op == "push"){
            int x;
            cin >> x;
            q[++tt] = x;
        }
        if(op == "pop") hh++;
        if(op == "empty"){
            if(hh <= tt) cout << "NO" << endl;
            else cout << "YES" << endl;
        }
        if(op == "query") cout << q[hh] << endl;
    }
    return 0;
}

队列用数组实现的模板题，推荐完全背下来。