Largest Rectangle in Histogram

原题链接Largest Rectangle in Histogram

给定一个直方图，计算这个直方图中最大的矩形面积。输入的是直方图中每个柱的高度

首先可以想到要求面积就需要确定矩形的高度，但是每个柱子的高度是不一样的，而不同的柱子组成的矩形要以最短的那个作为高

那么，是否可以对每个高度的分别计算面积呢？简单的说就是以每个柱子的高度作为最后矩形的高度，计算形成的最大矩形的面积

隐含的方法就是对于每个柱子，它的高度记为H，需要

• 向左找第一个高度小于H的柱子位置，下标记为l
• 向右找第一个高度小于H的柱子位置，下标记为r

那么，以H作为高的矩形的宽为(r - l - 1)，面积为(r - l - 1) * H

只需要把所有这样的面积求出来取最大值即可

代码如下

class Solution {
public:int largestRectangleArea(vector<int>& heights) {int maxArea = 0;for(int i = 0; i < heights.size(); ++i){/* 向左找第一个小于当前高度的位置 */int l = i - 1;while(l >= 0 && heights[l] >= heights[i])--l;/* 向右找第一个小于当前高度的位置 */int r = i + 1;while(r < heights.size() && heights[r] >= heights[i])++r;/* 计算面积 */maxArea = std::max(maxArea, (r - l - 1) * heights[i]);}return maxArea;}
};

但是，这种方法超时了:(
可以想到时间主要都消耗在内部的两个while循环，其实循环目的没错，为了寻找矩形的左右边界，但是试想，如果heights中所有元素都相等(极端情况)，那么每次while循环可能都需要遍历整个heights直到l < 0或者r >= heights.size()

可以从这两方面入手，考虑如何优化两个while循环

先考虑寻找左边界时的优化

假设需要找heights[i]的左边界，根据上述方法，需要一次遍历

i-1, i-2, ..., k1

找到第一个k1满足

heights[k1] < heights[i]

在下次循环中(i = i + 1)，又需要找heights[i+1]的左边界，同样的遍历方法

i, i-1, i-2, ..., k2

找到第一个k2满足

heights[k2] < heights[i+1]

仔细观察这两次循环，实际上是存在重复部分的，在找heights[i+1]的左边界过程中，假设有

heights[i] >= heights[i+1]

那么下次其实不需要从i-1开始继续比较heights[i-1] >= heights[i+1]，因为当遍历i+1时，有些东西是已知的，那就是

• 第一个小于heights[i]的位置，即k1

由于heights[i] >= heights[i+1]，从i, i-1, …, k+1这些位置上的元素一定也都大于等于heights[i+1]，那么为什么不从k1开始比较呢，是吧:)

当然这种方法是建立在对heights的遍历是从左向右的，即

for(int i = 0; i < heights.size(); ++i)...//寻找heights[i]的左边界

对于右边界，就需要让heights的遍历从右向左

for(int i = heights.size() - 1; i >= 0; --i)...//寻找heights[i]的右边界

最后再来一次循环，但是这次heights[i]的左边界和右边界都是已知的

class Solution {
public:int largestRectangleArea(vector<int>& heights) {if(heights.empty())return 0;int n = heights.size();vector<int> L(n, 0);vector<int> R(n, 0);for(int i = 0; i < n; ++i){int l = i - 1;while(l >= 0 && heights[l] >= heights[i])l = L[l];   //直接从k1开始找L[i] = l;}for(int i = n - 1; i >= 0; --i){int r = i + 1;while(r < n && heights[r] >= heights[i])r = R[r];   //直接从k1开始找R[i] = r;}int maxArea = 0;for(int i = 0; i < n; ++i){//L[i]表示左边第一个小于heights[i]的位置//R[i]表示右边第一个小于heights[i]的位置maxArea = std::max(maxArea, (R[i] - L[i] - 1) * heights[i]);}return maxArea;}
};

当然啦，如果觉得for循环有点多，可以把后两个合在一起:)

class Solution {
public:int largestRectangleArea(vector<int>& heights) {if(heights.empty())return 0;int n = heights.size();vector<int> L(n, 0);vector<int> R(n, 0);for(int i = 0; i < n; ++i){int l = i - 1;while(l >= 0 && heights[l] >= heights[i])l = L[l];   //直接从k1开始找L[i] = l;}int maxArea = 0;for(int i = n - 1; i >= 0; --i){int r = i + 1;while(r < n && heights[r] >= heights[i])r = R[r];   //直接从k1开始找R[i] = r;maxArea = std::max(maxArea, (R[i] - L[i] - 1) * heights[i]);}return maxArea;}
};

其实通常首先想到的就是最开始那个一个for循环，内部两个while找左右边界的版本，但是实际上while循环是可以优化的，如果知道优化的方法(找到重复计算的原因)，效率会高很多

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！