算法日记 - 单调栈五连

LC 739. 每日温度

739. 每日温度 - 力扣（LeetCode）

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int len = temperatures.size();
        if (len == 1) return vector<int>(1,0);
        vector<int> ans(len,0);
        stack<int> st;
        st.push(0);
        for(int i = 0; i < len; ++ i)
        {
            // 栈不为空的情况下 -- 发现当前元素比栈顶元素大：
            // 开始逐个计算栈顶元素和当前元素的距离(栈顶元素几天后会出现高温)，弹栈
            while(!st.empty() && temperatures[i] > temperatures[st.top()])
            {
                // 计算距离
                ans[st.top()] = i - st.top();
                // 弹栈
                st.pop();
            }
            st.push(i);
        }
        return ans;
    }
};

LC 496. 下一个更大元素 I

496. 下一个更大元素 I - 力扣（LeetCode）

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        int len = nums1.size(), len2 = nums2.size();
        if (len == 1 && len2 == 1) return vector<int>(1,-1);
        stack<int> st;
        vector<int> ans(len);
        unordered_map<int,int> nums_map;
        st.push(nums2[0]);

        for(int i = 1; i < len2; ++ i)
        {
            // num1 = [1,3,5,2,4]
            // num2 = [6,5,4,3,2,1,7]
            // 用while 不用if 是针对这种测试用例(在右相邻位但在右侧)
            while(!st.empty() && st.top() < nums2[i])
            {
                nums_map[st.top()] = nums2[i];
                st.pop();
            }
            st.push(nums2[i]);
        }
        while(!st.empty()){
            nums_map[st.top()] = -1;
            st.pop();
        }
        for(int i = 0; i < len; ++ i)
            ans[i] = nums_map[nums1[i]];
        ans.shrink_to_fit();
        return ans;        
    }
};

LC 503. 下一个更大元素 II

503. 下一个更大元素 II - 力扣（LeetCode）

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int len = nums.size();
        vector<int> ans(len,-1);
        if (len == 1) return ans;
        stack<int> st;
        for(int i = 2 *len - 1; i >= 0; --i)
        {
            while(!st.empty() && st.top() <= nums[i % len])
                st.pop();
            ans[i % len] = st.empty() ? -1 : st.top();
            st.push(nums[i % len]);
        }
        return ans;
    }
};

LC 42. 接雨水

42. 接雨水 - 力扣（LeetCode）

class Solution {
public:
    int trap(vector<int>& height) {
        int current = 0, sum = 0;
        std::stack<int> st;
        while (current < (int)height.size())
        {
            while (!st.empty() && height[st.top()] < height[current])
            {
                int h = height[st.top()];
                st.pop();
                if (st.empty()) break;
                
                int distance = current - st.top() -1;
                int min = std::min(height[st.top()], height[current]);
                sum += (distance * (min - h));
            }

            st.push(current);
            ++current;
        }
        return sum;
    }
};

LC 84. 柱状图中最大的矩形

84. 柱状图中最大的矩形 - 力扣（LeetCode）

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
    std::stack<int> stack;
    stack.push(-1); // 初始化栈，压入一个哨兵值
    int n = heights.size();
    int ans = 0; // 用于记录最大面积

    for (int i = 0; i < n; ++i) {
        // 当栈不为空且当前高度小于栈顶索引对应的高度时
        while (stack.size() > 1 && heights[stack.top()] > heights[i]) {
            int topIndex = stack.top(); // 取出栈顶元素
            stack.pop();
            int height = heights[topIndex];
            // 计算以height为高的矩形面积，并更新最大面积
            ans = std::max(ans, (i - stack.top() - 1) * height);
        }
        stack.push(i); // 将当前索引压入栈
    }

    // 处理栈中剩余的索引
    while (stack.size() > 1) {
        int topIndex = stack.top();
        stack.pop();
        int height = heights[topIndex];
        ans = std::max(ans, (n - stack.top() - 1) * height);
    }

    return ans;
    }
};

解法二:

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        // Solution:
        // 看官方题解（方法二：单调栈 + 常数优化）https://leetcode.cn/problems/largest-rectangle-in-histogram/ PPT 写代码...
        int len = heights.size(), maxArea = 0, area = 0, topIndex = 0;
        stack<int> st;
        st.push(-1);
        for (int i = 0; i < len; ++ i)
        {
            // 当栈不为空且当前高度小于栈顶索引对应的高度时
            while(st.size() > 1 && heights[st.top()] > heights[i])
            {
                topIndex = st.top();
                st.pop();
                // 计算以height为高的矩形面积，并更新最大面积
                area = (i - st.top() - 1) * heights[topIndex];
                maxArea = max(maxArea,area);
            }
            st.push(i);
        }

        while(st.size() > 1)
        {
            topIndex = st.top();
            st.pop();
            area = (len - st.top() - 1) * heights[topIndex];
            maxArea = max(maxArea,area);
        }
        return maxArea;
    }
};