LeetCode#84-柱状图中最大的矩形

题目描述(传送门)¹

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 求在该柱状图中，能够勾勒出来的矩形的最大面积。 以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。 图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

题目分析

在拿到该题目，我们首先需要分析，怎么才能找到最大的矩形呢？通过观察，可以看出，要考虑到所有情况，需要找到能够完全覆盖每个柱子的最大矩形，就像木桶效应一样，决定木桶装水的多少总取决于最短的那块木板。如下图所示：

观察每个柱状图可知，要想找到每个完全覆盖每个柱子的最大矩形，则需要找到每个柱子左边的比该柱子小的第一根柱子和每个柱子右边的比该柱子小的第一根柱子，找到这样两个边界之后，就可以确定完全覆盖该柱子的最大矩形的面积，即该柱子的高度乘以两个边界之差。

但是注意到最右边和最左边都没有更短的柱子了，所以此处可以假设其高度为0(灰色填充的柱子)。方便后面设计算法的时候理解长度计算方法。

算法设计

核心数据结构——单调栈(递增)

建立单调栈s存放每个柱子高度所在height数组的索引

遍历柱状图的柱子高度数组height[] 栈空 || 当前高度height[i] > height[s.top()]，将i压栈；循环，只要–栈不空 && 当前高度height[i] < height[s.top()]， 栈顶元素出栈，并更新最大矩形面积rectArea；矩形面积的计算方法：height[刚出栈的元素] * (i - s.top() - 1)，(i是刚出栈元素所在柱子的右边界，s.top()是刚出栈元素所在柱子的左边界)，此处需要注意，在进行长度计算的时候，由于栈顶元素出栈，可能造成此时栈空，所以需要讨论栈空的情况，若栈空则说明此时的i就是刚出栈元素的右边界，左边界可以当成0号柱子左边的-1号虚拟柱子（高度为0）,这样矩形的面积计算方法是height[刚出栈的元素] * (i - (-1) - 1) => i。跳出循环之后，将i压栈。 上面的步骤将所有元素都进行了入栈操作，但不一定都进行了出栈操作(栈中一定还剩元素，最小的肯定没有出栈)，所以此时需要将栈中的元素出栈，在出栈过程中，还需要实时更新最大矩形的面积，但此时还需要注意，栈中最后一个元素出栈之后，栈空，因为是单调栈，所以它是最小的一个元素，那么它的右边界可以当成5号柱子右边的6号虚拟柱子（高度为0），那么此时的矩形面及计算方法是height[最后出栈的元素] * (len - (-1) - 1) => len。返回最大矩形面积。

C++代码实现

class Solution { public: int largestRectangleArea(vector<int>& height) { stack<int> si;//用栈存放直方图高度所在的索引 int rectArea = 0; //矩形面积 int len = height.size(); for (int i = 0; i < len; i++) { if (si.empty() || height[si.top()] < height[i]) { si.push(i);//栈空 或者 当前元素比栈顶元素大 压栈 } else //栈不空 并且 当前元素比栈顶元素小 出栈 { //只要栈不空 并且当前元素小于栈顶元素 一直出栈 并更新最大矩形面积 while (!si.empty() && height[si.top()] > height[i]) { int idx = si.top();//当前栈顶元素 si.pop();//当前栈顶元素出栈 //计算矩形面积 并更新 rectArea = max(rectArea, height[idx] * (si.empty() ? i : i - si.top() - 1)); } si.push(i);//退出循环 si.top()< height[i] 或者栈空 也需要压栈i } } //所有元素都处理结束(压栈 或者 出栈了) while (!si.empty())//栈中还有剩余元素没有出栈 此时需要注意计算矩形长度时 要用height.size() { int idx = si.top(); si.pop(); rectArea = max(rectArea, height[idx] * (si.empty() ? len : len - si.top() - 1)); //rectArea = max(rectArea, height[idx] * len);//此时栈中只剩最小的一个了 因此需要乘以所有柱状图个数 } return rectArea; } };

---

题目来源：力扣（LeetCode） ↩︎