单调栈 && 单调队列

单调栈

• 最常用应用场景：找到每一个数左/右边离它最近的比它小/大的数
• 思考思路类似双指针，先考虑朴素暴力做法，再寻找特征，优化方案

单调栈

//ios比scanf和printf慢很多！！！

#include <iostream>

using namespace std;

const int N = 100010;

int n;
int stk[N], tt;//用数组模拟栈

int main() {
    cin >> n;
    
    for(int i = 0; i < n; i++) {
        int x;
        cin >> x;
        while(tt && stk[tt] >= x)tt--;//如果栈顶元素比当前元素大，直接弹出
        if(tt) cout << stk[tt] <<‘ ‘;//此时的栈顶元素就是目标元素
        else cout << -1 << ‘ ‘;//左边没有小于当前值的元素
        
        stk[ ++ tt]  = x;//将当前元素入栈
    }
    
    return 0;
}

单调栈 && 单调队列

原文：https://www.cnblogs.com/huhu555/p/14657154.html