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

水池问题: 给定一组高度,如[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;
    }
}