代码随想录算法训练营DAY57|C++单调栈Part3|84.柱状图中的最大矩形

84.柱状图中的最大矩形

力扣题目链接

文章链接：84.柱状图中的最大矩形

视频链接：单调栈，又一次经典来袭！ LeetCode：84.柱状图中最大的矩形

对于例子：

对于index=1,height[index]=1该位置而言，我们找右边第一个比它小的元素，没有，我们计算右边边界index=5，左边也没有，左边界index=0，所以该矩阵的高度为1，宽度为5+1，所以面积为6；

对于index=2,height[index]=5该位置而言，我们找右边第一个比它小的元素为2，index=4，左边第一个比它小的元素index=1，所以我们的矩阵高度为5，并且通过下标位置可以计算宽度为(4-1)-1=2，所以面积为10；

再说index=3,height[index]=6呢？左边第一个比它小的元素为5，index=2，右边第一个比它小的元素为2，index=4，所以高度为6，宽度为(4-2)-1=1，面积为6。

所以对于每一个柱子而言，我们都去找左边比它矮的，右边比它矮的，这样我们可以确定它的宽，然后该柱子的高我们肯定是可以知道的，所以就可以计算出在这个柱状图中 ，该柱子形成的矩形面积。最后选择一个最大的即可。

本题可以用暴力解法（一个for循环去遍历以每一个柱子为基准，然后for循环里面还有一个for循环去寻找左边比它矮的柱子，再去寻找右边比它矮的柱子），但是超时，因为需要$O(n^2)$的时间复杂度；

那么我们就可以着手想优化方法了：

双指针法、单调栈，本文只重点讨论单调栈的方法，关于双指针解法见卡哥文章：84.柱状图中的最大矩形

在接雨水题目中，我们是找每个柱子左右两边第一个大于该柱子高度的柱子，而本题是找每个柱子左右两边第一个小于该柱子的柱子。

单调栈思路

本题既然要求右边第一个比它小的元素，很明显需要使用递减栈。

单调栈内的重点其实还是三个元素，以哪一个柱子为基准(mid=st.top)、左边第一个比它小的柱子是哪个(left)、右边第一个比它小的柱子是哪个(right)。

跟接雨水的题目一样，左边第一个比基准元素小的就在栈内，所以需要

st.pop();
left = st.top()
right = i //表示当前遍历的元素
//求高
h = height(mid);
//求宽
w = right - left - 1;
//取每一个基准面积的最大值为本题答案
max(h*w);

首尾加个零

我们为什么要在末尾位置加个零呢？

例子：[2, 4, 6, 8]，那么我们入栈的话，「栈顶[8,6,4,2]栈底」，我们竟然很顺利直接全部元素都入栈，全程没有触发我们的当前元素比栈顶元素小的情况。然而我们计算结果的情况就是当前元素比栈顶元素小风时候，所以我们必须在末尾位置加一个0，所以他会跟栈内每一个元素为基准计算一次

我们为什么要在首位置加一个零呢？

其实就是出现数组第一个元素就需要来计算结果，我们必须得有一个左边的元素来作为左边比它矮的柱子。

处理代码

heights.insert(heights.begin(), 0); // 数组头部加入元素0
heights.push_back(0); // 数组尾部加入元素0
st.push(0);

CPP代码

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;
    }
};

//精简版代码
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st;
        heights.insert(heights.begin(), 0); // 数组头部加入元素0
        heights.push_back(0); // 数组尾部加入元素0
        st.push(0);
        int result = 0;
        for (int i = 1; i < heights.size(); i++) {
            while (heights[i] < heights[st.top()]) {
                int mid = st.top();
                st.pop();
                int w = i - st.top() - 1;
                int h = heights[mid];
                result = max(result, w * h);
            }
            st.push(i);
        }
        return result;
    }
};

单调栈总结

二刷回来搞总结