基本题目

739. 每日温度

需要找下一个更大的元素：逆向遍历，严格单调递减栈，弹出直到栈顶元素更大，最终修改结果

也可以正向遍历，严格单调递减栈，在弹出时修改结果

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        stack<int> s;
        s.push(n - 1);

        vector<int> result(n, 0);
        for (int i = n - 2; i >= 0; i--) {
            while (!s.empty() && temperatures[i] >= temperatures[s.top()]) s.pop();
            if (!s.empty()) result[i] = s.top() - i;
            s.push(i);
        }
        return result;
    }
};

496. 下一个更大元素 I

更大元素：单调递减栈，两边遍历均可

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int> s;
        unordered_map<int, int> nextGreater;

        for (const int &num : nums2) {
            while (!s.empty() && s.top() < num) {
                nextGreater[s.top()] = num;
                s.pop();
            }
            s.push(num);
        }
        while (!s.empty()) {
            nextGreater[s.top()] = -1;
            s.pop();
        }

        vector<int> result(nums1.size());
        for (int i = 0; i < nums1.size(); i++) {
            result[i] = nextGreater[nums1[i]];
        }
        return result;
    }
};

503. 下一个更大元素 II

单调递减栈，遍历两次来考虑循环情况

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n, INT_MIN);
        stack<int> s;

        for (int i = n - 1; i >= 0; i--) {
            while (!s.empty() && s.top() <= nums[i]) s.pop();
            if (!s.empty()) result[i] = s.top();
            s.push(nums[i]);
        }
        for (int i = n - 1; i >= 0; i--) {
            if (result[i] == INT_MIN) {
                while (!s.empty() && s.top() <= nums[i]) s.pop();
                if (!s.empty()) result[i] = s.top();
                else result[i] = -1;
            }
        }

        return result;
    }
};

42. 接雨水

每列分别计算：左侧最大值、右侧最大值、当前列高度

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();

        // Find left max
        vector<int> leftMax(n, height[0]);
        for (int i = 1; i < n; i++) {
            leftMax[i] = max(leftMax[i - 1], height[i]);
        }

        // Find right max
        int rightMax = 0;
        int result = 0;
        for (int i = n - 1; i >= 0; i--) {
            rightMax = max(rightMax, height[i]);
            result += max(min(rightMax, leftMax[i]) - height[i], 0);
        }

        return result;
    }
};

可以使用双指针来替代数组预存储一侧的最大值，同时维护左侧右侧的最大值

正确性证明：移动左侧指针（左小于右）并计算深度时，其使用到的右侧最大值一定至少为右指针的高度，而此时左侧最大值一定是不大于右指针高度的（否则会左指针会停在左侧最大值，一直移动右指针），所以计算深度可以直接使用左侧最大值。

class Solution {
public:
    int trap(vector<int>& height) {
        int left = 0, right = height.size() - 1;
        int leftMax = 0, rightMax = 0;
        int result = 0;
        while (left < right) {
            if (height[left] < height[right]) {
                result += max(leftMax - height[left], 0);
                leftMax = max(leftMax, height[left]);
                left++;
            }
            else {
                result += max(rightMax - height[right], 0);
                rightMax = max(rightMax, height[right]);
                right--;
            }
        }
        return result;
    }
};

逐层叠加：单调递减栈，遇到较大元素时表示出现水槽，填充对应深度

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        stack<int> s;

        int result = 0;
        for (int i = 0; i < n; i++) {
            int prev = 0;
            while (!s.empty()) {
                result += (min(height[i], height[s.top()]) - prev) * (i - s.top() - 1);
                prev = height[s.top()];
                if (prev > height[i]) break;
                s.pop();
            }
            s.push(i);
        }
        return result;
    }
};

84. 柱状图中最大的矩形

单调栈算两次，分别计算左侧与右侧的下一个更小元素

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        vector<int> smallerLeft(n), smallerRight(n);

        // First smaller element to the left
        stack<int> s;
        for (int i = 0; i < n; i++) {
            while (!s.empty() && heights[s.top()] >= heights[i]) s.pop();
            smallerLeft[i] = s.empty() ? 0 : s.top() + 1;
            s.push(i);
        }

        // First smaller element to the right
        while (!s.empty()) s.pop();
        for (int i = n - 1; i >= 0; i--) {
            while (!s.empty() && heights[s.top()] >= heights[i]) s.pop();
            smallerRight[i] = s.empty() ? n : s.top();
            s.push(i);
        }

        // Calculate sizes
        int largestSize = 0, size;
        for (int i = 0; i < n; i++) {
            size = (smallerRight[i] - smallerLeft[i]) * heights[i];
            largestSize = max(size, largestSize);
        }
        return largestSize;
    }
};

将两次遍历合并后，计算结果变为了右侧的下一个不大于它的元素。这对最终的结果没有影响：最右侧的相等高度柱形可以得到正确的结果

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        vector<int> smallerLeft(n), smallerRight(n, n);

        // First smaller element to the left & right
        stack<int> s;
        for (int i = 0; i < n; i++) {
            while (!s.empty() && heights[s.top()] >= heights[i]) {
                smallerRight[s.top()] = i;
                s.pop();
            }
            smallerLeft[i] = s.empty() ? 0 : s.top() + 1;
            s.push(i);
        }

        // Calculate sizes
        int largestSize = 0, size;
        for (int i = 0; i < n; i++) {
            size = (smallerRight[i] - smallerLeft[i]) * heights[i];
            largestSize = max(size, largestSize);
        }
        return largestSize;
    }
};