单调栈

核心思想

单调栈处理”某个元素，距它最近的、比它大/小的元素在哪里”这类问题。

最原始的问题形态

给一个数组，对每个元素，找：

左边第一个比我大的    左边第一个比我小的
右边第一个比我大的    右边第一个比我小的

暴力是 $O(n^2)$，单调栈是 $O(n)$。

---

为什么单调栈能做到？

以”右边第一个比我大的”为例：

nums = [3, 1, 4, 2, 5]

维护一个单调递减栈（存下标）：

处理 3：栈 = [3]
处理 1：1 < 3，压栈。栈 = [3, 1]
处理 4：4 > 1，弹出 1 → "1 的右边第一个更大值 = 4" ✓
        4 > 3，弹出 3 → "3 的右边第一个更大值 = 4" ✓
        压栈。栈 = [4]
处理 2：2 < 4，压栈。栈 = [4, 2]
处理 5：5 > 2，弹出 2 → "2 的右边第一个更大值 = 5" ✓
        5 > 4，弹出 4 → "4 的右边第一个更大值 = 5" ✓
        压栈。栈 = [5]

关键机制：一个元素被弹出的那一刻，正好是它的”答案”出现的时刻。

---

例题

Leetcode .3660

通过维护一个递增栈，寻找左边第一个比当前值大的位置，出栈并合并到一个区间中。这样栈到最后就会变成几个不同的无法合并的区间。每个区间取最大值就是最终答案。

struct Item {
    int mx;
    int mi;
    int le;
    int len;
};
 
class Solution {
public:
    vector<int> maxValue(vector<int>& nums) {
        vector<Item> s;
        int n = nums.size();
        for (int i = 0; i < n; i ++ ) {
            int min_v = nums[i];
            int max_v = nums[i];
            int l = i;
            while (!s.empty() && s.back().mx > min_v) {
                auto [top_max, top_min, le, len] = s.back(); s.pop_back();
                min_v = min(top_min, min_v);
                max_v = max(top_max, max_v);
                l = le;
            }
            s.push_back(Item{max_v, min_v, l, i - l + 1});
        }
        vector<int> ans(n);
 
        for (auto [top_max, top_min, le, len] : s) {
            for (int i = 0; i < len; i ++ ) {
                ans[le + i] = top_max;
            }
        }
        return ans;
    }
};