使用场景

O(N)地找到“离我最近且比我大/小的那个元素”

原理

以离我最近且比我大的那个元素为例，每次遍历至新元素时，把前面的小于等于自己的元素弹出，由于是按从左向右顺序入栈的，弹出后栈顶的元素自然就是大于自己且左边离自己最近的元素了

例题

int largestRectangleArea(vector<int>& heights) {
    int n = heights.size();
    vector<int> left(n), right(n);
    vector<int> stk;
    for (int i = 0; i < n; i++) {
        while (!stk.empty() && heights[stk.back()] >= heights[i]) {
            stk.pop_back();
        }
        left[i] = stk.empty() ? -1 : stk.back();
        stk.push_back(i);
    }
    stk.clear();
    for (int i = n - 1; i >= 0; i--) {
        while (!stk.empty() && heights[stk.back()] >= heights[i]) {
            stk.pop_back();
        }
        right[i] = stk.empty() ? n : stk.back();
        stk.push_back(i);
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int l = left[i], r = right[i];
        int t = (r - l - 1) * heights[i];
        ans = max(ans, t);
    }
    return ans;
}

E - Water Tank

void solve() {
    int N;
    cin >> N;
    vector<int> H(N + 1);
    H[0] = inf;
    for (int i = 1; i <= N; i++) {
        cin >> H[i];
    }

    vector<int> stk = {0};
    i64 las = 0;
    vector<i64> ans(N + 1);
    for (int i = 1; i <= N; i++) {
        while (!stk.empty() && H[stk.back()] < H[i]) {
            stk.pop_back();
        }
        ans[i] = ans[stk.back()] + 1LL * H[i] * (i - stk.back());
        cout << ans[i] + 1 << " \n"[i == N];
        stk.push_back(i);
    }
}