单调栈结构

单调栈，顾名思义，栈中的内容是单调的，我们可以利用这里特性解决一些有趣的问题，如：

水池问题: 给定一组高度，如[0,1,0,2,1,0,1,3,2,1,2,1]，返回可以装的水量6

最大面积问题：给定一组高度如[2,1,5,6,2,3]，返回最大矩形面积10

题目中要求所有值左边👈和右边👉最近的较小值，可以利用单调递增栈：

1. 如果当前元素大于栈顶元素，将元素下标入栈
2. 如果当前元素小于栈顶元素，一一出栈，直到栈顶下标对应元素大于当前元素，然后将当前元素的下标入栈
3. 出栈的过程中，第一个栈顶即为当前元素左边的较小值，剩下的栈顶对应元素的右边较小值为当前元素

遍历完整个数组后，如果栈不为空，一一出栈，此时下标对应的元素无右边较小值，左边较小值为下一个栈顶对应的数组元素。

代码如下：

//
// Created by jt on 2020/8/27.
//
#include <iostream>
#include <vector>
#include <stack>
using namespace std;


int main() {
    int n;
    cin >> n;
    vector<int> vec;
    for (int i = 0; i < n; ++i) { int a; cin >> a; vec.push_back(a); }
    stack<int> st;  // 单调递增栈
    vector<int> left(n, -1), right(n, -1);  // 分别存储左边较小值和右边较小值的下标
    for (int i = 0; i < n; ++i) {
        while(!st.empty() && vec[i] < vec[st.top()]) {
            int cur = st.top(); st.pop();
            if (!st.empty()) left[cur] = st.top();
            right[cur] = i;
        }
        st.push(i);  // 将当前元素的下标入栈
    }
    while(!st.empty()) {
        int cur = st.top(); st.pop();
        if (!st.empty()) left[cur] = st.top();
    }
    for (int i = 0; i < n; ++i) {
        cout << left[i] << ' ' << right[i] << endl;
    }
}