首页 > 代码库 > Leetcode#84 Largest Rectangle in Histogram
Leetcode#84 Largest Rectangle in Histogram
原题地址
有两种方法，左右扫描或辅助栈。
1. 左右扫描法
考虑到最大面积的矩形高度一定跟某个条一样高，所以挨个枚举每个条，看其向左、向右最多能延伸到多远。在计算左右边界时，可以借助之前计算过的结果迭代（类似动归的感觉）优化以减少时间复杂度，这应该算是唯一的难点了。总的来说，向左一遍，向右一遍，整体求面积再一遍，一共需要3次遍历，时间复杂度是O(n)。
推荐采用左右扫描法，因为非常直观，特殊情况少，不容易出错。
代码：
1 int largestRectangleArea(vector<int> &height) { 2 if (height.empty()) return 0; 3 4 int n = height.size(); 5 int maxArea = 0; 6 int *left = new int[n]; // 向左能延伸多远 7 int *right = new int[n]; // 向右能延伸多远 8 9 // 向右延伸10 right[n - 1] = 1;11 for (int i = n - 2; i >= 0; i--) {12 if (height[i] > height[i + 1])13 right[i] = 1;14 else {15 int j = i + 1;16 while (j < n && height[j] >= height[i])17 j += right[j];18 right[i] = j - i;19 }20 }21 22 // 向左延伸23 left[0] = 1;24 for (int i = 1; i < n; i++) {25 if (height[i] < height[i - 1])26 left[i] = 1;27 else {28 int j = i - 1;29 while (j >= 0 && height[j] >= height[i])30 j -= left[j];31 left[i] = i - j;32 }33 }34 35 // 求面积36 maxArea = height[0];37 for (int i = 0; i < n; i++) {38 maxArea = max(height[i] * (left[i] + right[i] - 1), maxArea);39 }40 41 return maxArea;42 }
2. 辅助栈法（网上很多人采用的方法）
分两个步骤进行：
第一步，算出以每个条为右边界（既是右边界，又是上边界）所能达到的最大矩形面积，依次压栈。这一步相当于是在延伸左边界，但是左边界的计算过程体现在第二步里了。
第二步，依次弹栈，将每个矩形条向右延伸至最远，以这个条的高度为高度的最大面积。这一步相当于在延伸右边界。
所以，本质上和左右扫描法是一样的。为了保证算法的正确性，需要考虑很多情况。
对于第一步，可以分两种情况：
如果当前条比之前的条要高，除了入栈什么都不用做，它的面积后面会算到，如下图所示：
如果当前条比之前的条矮，那就需要不断向左延伸直到找到最远边界。当然，这同样是个迭代过程。不过，这里有一点小优化：既然我们已经知道了当前条的高度比前一个条要矮，那么，以前一个条为高的矩形也就到它那为止了，不可能延伸到当前这个矮条上来（下图中左边的两个矩形条）。所以，我们可以立刻得到前一个条为高的最大矩形的面积（下图中带颜色的两个矩形）！既然我们算出了前一个条最大矩形的面积，那么也就没必要再留着它了。所以，可以放心把它删掉，或者说合并。
第二步其实相当简单，因为如果按照第一步的处理方法，到第二步的时候，栈里面所有的条肯定是按照高度依次递增的。就像这样：
所以，对于任何一个矩形条，我们可以确定，它的右边界一定是整个栈里所保留的条形图的最右边界，而它的左边界一定是它这个条自己的左边界，所以，面积立刻就可以算出来了。
第一步需要遍历一遍，第二步最坏情况下还要遍历一遍，所以一共两遍，时间复杂度是O(n)。
落实到代码中时，我们只需要在辅助栈保存矩形的右边界坐标即可，不需要保存高度，因为可以通过右边界坐标得到（height[i] ），也不需要保存左边界坐标，因为上一个矩形的右边界坐标+1就是当前矩形的左边界。
代码：
1 int largestRectangleArea(vector<int> &height) { 2 stack<int> st; 3 int n = height.size(); 4 int maxArea = 0; 5 int h, w; 6 7 // 第一步 8 for (int i = 0; i < n; i++) { 9 if (st.empty() || height[st.top()] < height[i])10 st.push(i);11 else {12 while (!st.empty() && height[i] <= height[st.top()]) {13 h = height[st.top()];14 st.pop();15 w = st.empty() ? i : i - (st.top() + 1);16 maxArea = max(maxArea, h * w);17 }18 st.push(i);19 }20 }21 22 // 第二步23 while (!st.empty()) {24 h = height[st.top()];25 st.pop();26 w = st.empty() ? n : n - (st.top() + 1);27 maxArea = max(maxArea, h * w);28 }29 30 return maxArea;31 }
Leetcode#84 Largest Rectangle in Histogram