「代码随想录算法训练营」第四十二天 | 单调栈 part2

42. 接雨水

题目链接:https://leetcode.cn/problems/trapping-rain-water/
文章讲解:https://programmercarl.com/0042.接雨水.html
题目难度:困难
视频讲解:https://www.bilibili.com/video/BV1uD4y1u75P/
题目状态:这道题目在LeetCode Top100中做过,使用两种方法,再回顾一下

思路一:单调栈

  1. 栈的作用

    • 栈用于存储柱子的索引,确保栈中的高度是递减的。
  2. 遍历数组

    • 对于每个柱子,如果当前柱子高度大于栈顶柱子高度,说明可以形成一个凹槽来积水。
  3. 计算积水

    • 弹出栈顶元素,作为凹槽的底部。
    • 如果栈为空,说明没有左边界,无法积水。
    • 否则,计算左边界(新的栈顶)与当前柱子之间的宽度。
    • 计算高度差:min(height[left], height[i]) - height[top]
    • 计算当前积水量并累加到结果中。
  4. 继续遍历

    • 将当前柱子的索引压入栈中,继续处理下一个柱子。

代码一:

class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0;
        stack<int> stk;
        int n = height.size();
        for(int i = 0; i < n; ++i) {
            while(!stk.empty() && height[i] > height[stk.top()]) {
                int top = stk.top();
                stk.pop();
                if(stk.empty()) break;
                int left = stk.top();
                int currWidth = i - left - 1;
                int currHeight = min(height[left], height[i]) - height[top];
                ans += currWidth * currHeight;
            }
            stk.push(i);
        }
        return ans;
    }
};

消耗一:

思路二:动态规划

  1. 初始化

    • 检查输入数组是否为空。如果是,直接返回0。
  2. 计算左边最大高度

    • 创建一个数组 leftMax,其中 leftMax[i] 存储从位置0到位置i的最大高度。
    • 通过遍历数组,逐步更新 leftMax
  3. 计算右边最大高度

    • 创建一个数组 rightMax,其中 rightMax[i] 存储从位置i到数组末尾的最大高度。
    • 通过反向遍历数组,逐步更新 rightMax
  4. 计算总积水量

    • 遍历每个位置,计算当前位置能存储的水量:min(leftMax[i], rightMax[i]) - height[i]
    • 将每个位置的水量累加到总水量中。
  5. 返回结果

    • 返回总积水量。

代码二:

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        if(n == 0) return 0;
        
        vector<int> leftMax(n);
        leftMax[0] = height[0];
        for(int i = 1; i < n; ++i) {
            leftMax[i] = max(leftMax[i - 1], height[i]);
        }

        vector<int> rightMax(n);
        rightMax[n - 1] = height[n - 1];
        for(int i = n - 2; i >= 0; --i) {
            rightMax[i] = max(rightMax[i + 1], height[i]);
        }

        int ans = 0;
        for(int i = 0; i < n; ++i) {
            ans += min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }
};

消耗二:

84. 柱状图中最大的矩形

题目链接:https://leetcode.cn/problems/largest-rectangle-in-histogram/
文章讲解:https://programmercarl.com/0084.柱状图中最大的矩形.html
题目难度:困难
视频讲解:https://www.bilibili.com/video/BV1Ns4y1o7uB/
题目状态:不会做,看题解

思路一:双指针

  1. 初始化:

    • minLeftIndex[0] 初始化为 -1,表示最左边界。
    • minRightIndex[size - 1] 初始化为 size,表示最右边界。
  2. 计算 minLeftIndex:

    • 从左到右遍历柱子,对于每个柱子 i,向左寻找第一个高度小于 heights[i] 的柱子。
    • 使用变量 ti-1 开始向左查找,更新 minLeftIndex[i] 为找到的下标。
    • 如果当前柱子 t 的高度大于等于 heights[i],继续向左查找 minLeftIndex[t]
  3. 计算 minRightIndex:

    • 从右到左遍历柱子,对于每个柱子 i,向右寻找第一个高度小于 heights[i] 的柱子。
    • 使用变量 ti+1 开始向右查找,更新 minRightIndex[i] 为找到的下标。
    • 如果当前柱子 t 的高度大于等于 heights[i],继续向右查找 minRightIndex[t]
  4. 计算最大矩形面积:

    • 遍历每个柱子 i,计算以该柱子为高的最大矩形面积:heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1)
    • 更新 result 为所有计算出的矩形面积的最大值。
  5. 返回结果:

    • 返回 result,即最大矩形的面积。

代码一:

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int len = heights.size();
        vector<int> minLeftIndex(len);
        vector<int> minRightIndex(len);
        minLeftIndex[0] = -1;
        for(int i = 1; i < len; ++i) {
            int t = i - 1;
            while(t >= 0 && heights[t] >= heights[i]) t = minLeftIndex[t];
            minLeftIndex[i] = t;
        }
        minRightIndex[len - 1] = len;
        for(int i = len - 2; i >= 0; --i) {
            int t = i + 1;
            while(t < len && heights[t] >= heights[i]) t = minRightIndex[t];
            minRightIndex[i] = t;
        }
        int ans = 0;
        for(int i = 0; i < len; ++i) {
            int sum = heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1);
            ans = max(sum, ans);
        }
        return ans;
    }
};

消耗一:

思路二:单调栈

  1. 初始化栈:

    • 插入 0 后,栈中初始含有下标 0
  2. 遍历柱子:

    • 从下标 1 开始遍历 heights 数组。
  3. 处理情况:

    • heights[i] < heights[st.top()] 时,表示可以计算以栈顶柱子为高的矩形面积。
    • 不断弹出栈顶元素,直到栈为空或栈顶柱子高度不大于当前柱子高度。
    • 计算面积:
      • mid 是当前弹出的柱子下标。
      • w = i - st.top() - 1 是矩形的宽度。
      • h = heights[mid] 是矩形的高度。
      • 更新 result 为最大值。
  4. 返回结果:

    • 返回 result,即最大矩形的面积。

代码二:

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int ans = 0;
        stack<int> st;
        heights.insert(heights.begin(), 0);
        heights.push_back(0);
        st.push(0);
        for(int i = 1; i < heights.size(); ++i) {
            if(heights[i] >= heights[st.top()]) st.push(i);
            else {
                while(!st.empty() && heights[i] < heights[st.top()]) {
                    int mid = st.top();
                    st.pop();
                    if(!st.empty()) {
                        int left = st.top();
                        int right = i;
                        int w = right - left - 1;
                        int h = heights[mid];
                        ans = max(ans, w * h);
                    }
                }
                st.push(i);
            }
        }
        return ans;
    }
};

消耗二: