【2021.2.16】单调栈的应用

理解：给定数组a，当在第i个值时a[i]，寻找左侧距离当前元素最近的小于该元素a[i]的值。
设定一个栈，因此每次遍历一个元素a[i]时，只需要将其不断地与栈顶元素top进行比较，如果a[i] >= top，则说明此时的栈顶top是满足条件的，此时将a[i]入栈。否则如果a[i]<top，则说明此时栈顶元素不满足，则出栈（这些出栈的元素一定是大于等于当前元素a[i]，a[i+1]及其之后的元素要寻找的结果一定不会是这些被出栈的元素）。因此每次遍历一个元素，都会保证当前的栈内的元素（栈底到栈顶）是单调递增的

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

const int N = 1e5 + 5;
stack <long long> stk;
vector<long long> a;

int main() {
    int n;
    long long x;
    cin >> n;
    while(n --) {
        cin >> x;
        a.push_back(x);
    }
    stk.push(-1); // 添加一个-1标记，表示栈为空
    for(int i = 0; i < a.size(); i ++) {
        while(!stk.empty() && stk.top() >= a[i]) stk.pop();
        cout << stk.top() <<' ';
        stk.push(a[i]);
    }
    return 0;
}