单调栈

1 简介

单调栈就是一个栈中元素保持单调性

单调栈适合解决：求当前元素左或者右边第一个更大/小的元素

重点需要确定栈是递增（从栈顶向栈底看）还是递减的属性：递增求的是第一个比他大的元素

单调栈的作用是存放之前遍历过的数据，而数据的单调性有保证了一定不会漏掉之前已经放进来过的元素，这个过程比较巧妙，通过模拟一遍流程应该能能够理解这个步骤

单调栈的本质是当新元素 x 进来时，如果它比结构里的某些元素“更优”，那些元素就永远不可能再成为答案，所以可以直接去除了

2 题目节选

2.1 每日温度

LeeCode 739

单调栈入门题，为了保证我们能够获取到之前放入的数据的具体信息，我们需要放入的是下标，而通过下标我们可以同时访问到元素的值

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> stk; // 单调栈
        vector<int> ret(temperatures.size(), 0);
        stk.push(0);
        for (int i = 1; i < temperatures.size();) {
            int idx = 0;
            if (stk.empty()) {
                stk.push(i++);
                continue;
            } else {
                idx = stk.top(); 
            }
            if (temperatures[i] <= temperatures[idx]) {
                stk.push(i++);    // 入栈，下一个数检查
            } else {
                ret[idx] = i - idx; // 找到了某个数下一个最大值，更新 ret
                stk.pop();
                // 继续检查这个数是不是还有比他小的
            }
        }
        return ret;
    }
};

2.2 下一个更大的元素

LeetCode 496

哈希表 + 单调栈，并优化了一部分单调栈的循环逻辑

这里注意一下使用 vector 模拟栈的操作

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        // 简化逻辑，每个元素进行一次入栈和出栈
        unordered_map<int, int> mp;
        int m = nums1.size();
        mp.reserve(m);
        for (int i = 0; i < m; i++) {
            mp[nums1[i]] = i;
        }
        vector<int> ret(nums1.size(), -1);
        vector<int> stk;     // 这里不可以执行初始化大小
        stk.reserve(nums2.size() / 2);
        for (int& x : nums2) {
            while(!stk.empty() && x > stk.back()) {
                // 只有非空且大于 才需要弹出
                int val = stk.back();
                stk.pop_back();
                unordered_map<int, int>::iterator it = mp.find(val);
                if (it != mp.end()) {
                    ret[it->second] = x;
                }
            }
            // 终归需要放进去
            stk.push_back(x);
        }
        return ret;
    }
};

2.3 下一个更大的元素 II

LeeCode 503

1. 环的下标，可以用取模来进行模拟
2. 单调栈每一个数字只入栈一次，每个数字在出栈的时候对结果数组进行赋值

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> ret(n, -1);
        vector<int> stk;
        stk.reserve(n / 2);

        for (int i = 0; i < 2 * n - 1; i++) {
            int j = i % n;  // nums 的下标
            while (!stk.empty() && nums[j] > nums[stk.back()]) {
                int idx = stk.back();
                stk.pop_back();
                ret[idx] = nums[j];
            }
            if (i / n == 0) {
                // 只有第一次入栈
                stk.push_back(j);
            } 
        }
        return ret;
    }
};

2.4 接雨水

LeetCode 42

经典的单调栈题目，重点在于找到左右比他大（可以等于，其实不影响结果，因为都要减去中间柱子的高度）的值

这是单调栈的做法，其实同时找左右两边更大的只用一个栈就可以了，因为栈里面存放了已经访问过的元素的数据

class Solution {
public:
    int trap(vector<int>& height) {
        // 1. 单调栈计算所有更大的值的相对位置
        vector<int> higher(height.size(), -1);
        stack<int> stk;
        
        // 找右边大的（允许相等）
        for (int i = 0; i < height.size(); i++) {
            int curr = height[i];
            while (!stk.empty() && curr > height[stk.top()]) {
                int idx = stk.top();
                stk.pop();
                higher[idx] = i - idx;
            }
            stk.push(i);
        }
        
        int ret = 0;
        for (int i = 0; i < higher.size(); i++) {
            // 有 -1 就漏水
            if (higher[i] == -1) continue;
            // 对区间范围内全部累加 + 1
            ret += higher[i] - 1;
        }
        return ret;
    }
};

接雨水还有一种双指针的算法，这个在刷 Hot 100 时候再写

2.5 柱状图中的最大矩形

LeetCode 84

这里面混合一点点贪心的思想：最后的结果一定是某一个柱子的高度

为什么呢？因为如果不是某个柱子的高度的话，一定就可以再往上顶一顶，也就是说一定会把某一个柱子的高度吃满

要注意一下清空 栈的策略

这里写的比较复杂，实际有更简单一点的写法

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        // 从某一个柱子开始计算左右两边的最低点
        stack<int> stk;
        int n = heights.size();
        int ret = heights[0];
        for (int i = 0; i < n; i++) {
            int curr = heights[i];
            // 从栈顶看是单调递减的栈
            while(!stk.empty() && curr < heights[stk.top()]) {
                // 以 mid_idx 为核心高度，左右扩展计算面积
                int mid_idx = stk.top();
                int wide = 0;
                stk.pop();
                if (stk.empty()) {
                    // 左边没有更小的
                    wide = i;
                } else {
                    // 左边还有更小的
                    wide = i - stk.top() - 1;
                }
                // cout << wide << " * " << heights[mid_idx] << endl;
                ret = max(ret, wide * heights[mid_idx]);
            }
            stk.push(i);
            // cout << heights[i] << ' ' << ret << endl;
        }
        // 把栈里面的剩下的统计一下
        while(!stk.empty()) {
            int wide = 0;
            int mid_idx = stk.top();
            stk.pop();
            if (stk.empty()) {
                // 左边没有更小的了
                wide = n;
            } else {
                wide = n - stk.top() - 1;
            }
            ret = max(ret, wide * heights[mid_idx]);
        }
        return ret;
    }
};