More content：LeetCode hot100@栈

96. 下一个更大元素 I✅

单调栈 + 哈希

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> sk; //单调栈
        vector<int> res(temperatures.size(), 0);

        for(int i = 0; i < temperatures.size(); i++) {
            while(!sk.empty() && temperatures[i] > temperatures[sk.top()]) {
                res[sk.top()] = i - sk.top();
                sk.pop();
            }
            sk.push(i); //压入下标 
        }

        return res;
    }
};

496. 下一个更大元素 I✅

在上一题的基础上 先扩充一倍再缩减一倍

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        stack<int> sk;
        vector<int> v;
        vector<int> res(nums.size() * 2, -1);
        unordered_map<int, int> mp;

        for(const auto &i : nums) v.push_back(i);
        for(const auto &i : nums) v.push_back(i);

        for(int i = 0; i < v.size(); i++) {
            while(!sk.empty() && v[i] > v[sk.top()]) {
                res[sk.top()] = v[i];
                sk.pop();
            }
            sk.push(i);
        }
 
        res.resize(nums.size());

        return res;
    }
};

42. 接雨水❌

Solution1：双指针 (按列计算)

每一列雨水的高度取决于，该列左侧最高的柱子和右侧最高的柱子中较矮的那个柱子的高度 – 自身高度

Solution2：单调栈 (按行计算)

栈底到栈头元素递减，因为一旦要添加的柱子高度大于栈头元素，说明出现凹槽了

此时，栈头元素就是凹槽底部的柱子，栈头第二个元素就是凹槽左边的柱子，而添加的元素就是凹槽右边的柱子

class Solution1 {
public:
    int trap(vector<int>& height) {
        int res = 0;
        int len = height.size();
        //记录当前列的左右两边的最高列
        vector<int> lmax(len);
        vector<int> rmax(len);
        
        lmax[0] = height[0];
        for(int i = 1; i < len; i++) {
            lmax[i] = max(lmax[i-1], height[i]);
        }

        rmax[len - 1] = height[len - 1];
        for(int i = len - 2; i >= 0; i--) {
            rmax[i] = max(rmax[i+1], height[i]);
        }

        for(int i = 0; i < height.size(); i++) {
            int x = min(lmax[i], rmax[i]) - height[i]; //第一列和最后一列的x算出来是0           
            if(x > 0) res += x; //是正数才说明能接住雨水，负数的情况比如最高列
        }

        return res;
    }
};

class Solution2 {
public:
    int trap(vector<int>& height) {
        stack<int> sk; //存下标
        int res = 0;
        sk.push(0);

        for(int i = 1; i < height.size(); i++) {
            while(!sk.empty() && height[i] > height[sk.top()]) { //出现凹槽
                int mid = height[sk.top()]; //凹槽中间柱子高度
                sk.pop();
                if(!sk.empty()) {
                    int left = height[sk.top()]; //凹槽左边柱子高度
                    int right = height[i]; //凹槽右边柱子高度
                    int h = min(left, right) - mid;
                    int w = i - sk.top() - 1;
                    res += h * w; //高×宽
                }
            }
            sk.push(i);
        }

        return res;
    }
};