侧边栏壁纸
博主头像
thinkTV博主等级

喜爱动漫的二刺螈一枚,摩托车云爱好者(快要有车了)。 懂一点技术的在读生物医学工程研究生( •̀ ω •́ )✧,多多指教。

  • 累计撰写 127 篇文章
  • 累计创建 17 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

代码随想录算法训练营第六十天 | 柱状图中最大的矩形

thinkTV
2023-06-19 / 0 评论 / 0 点赞 / 147 阅读 / 634 字 / 正在检测是否收录...

1. 柱状图中最大的矩形

代码随想录:原文

力扣题目链接:84.柱状图中最大的矩形

1.1 思路

  • 本题和42. 接雨水思路相近
  • 42.接雨水 (opens new window)是找每个柱子左右两边第一个大于该柱子高度的柱子,而本题是找每个柱子左右两边第一个小于该柱子的柱子
  • 本题是要找每个柱子左右两边第一个小于该柱子的柱子,所以从栈头(元素从栈头弹出)到栈底的顺序应该是从大到小的顺序

主要就是分析清楚如下三种情况:

  • 情况一:当前遍历的元素heights[i]大于栈顶元素heights[st.top()]的情况
  • 情况二:当前遍历的元素heights[i]等于栈顶元素heights[st.top()]的情况
  • 情况三:当前遍历的元素heights[i]小于栈顶元素heights[st.top()]的情况

注意:数组首尾加零

  1. 末尾为什么要加元素0:
    • 如果数组本身就是升序的,例如[2,4,6,8],那么入栈之后 都是单调递减,一直都没有走 情况三 计算结果
    • 那么结尾加一个0,就会让栈里的所有元素,走到情况三的逻辑

图片-1

  1. 开头为什么要加元素0?
    • 如果数组本身是降序的,例如 [8,6,4,2],在 8 入栈后,6 开始与8 进行比较,此时我们得到 mid(8),rigt(6),但是得不到 left (mid、left,right 都是对应版本一里的逻辑)
    • 所以我们需要在 height数组前后各加一个元素0

图片-2

1.2 代码实现

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int result = 0;
        stack<int> st;
        heights.insert(heights.begin(), 0); // 数组头部加入元素0
        heights.push_back(0); // 数组尾部加入元素0
        st.push(0);

        // 第一个元素已经入栈,从下标1开始
        for (int i = 1; i < heights.size(); i++) {
            if (heights[i] > heights[st.top()]) { // 情况一
                st.push(i);
            } else if (heights[i] == heights[st.top()]) { // 情况二
                st.pop(); // 这个可以加,可以不加,效果一样,思路不同
                st.push(i);
            } else { // 情况三
                while (!st.empty() && heights[i] < heights[st.top()]) { // 注意是while
                    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];
                        result = max(result, w * h);
                    }
                }
                st.push(i);
            }
        }
        return result;
    }
};

完结撒花!

0

评论区