[LeetCode] Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

[LeetCode] Largest Rectangle in Histogram

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

[LeetCode] Largest Rectangle in Histogram

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

这题有两个解法,一个暴力O(n^2) 另一个是非常流弊聪明的O(n),两个都花了我很长时间去思考,最后看了这篇博文 才略有所得。
首先暴破在现在看来思路应该是很直观的,但是我当时还是一点头绪没有,故思考良久以后决定去找答案。先来看看暴力法。

min_h = 0
max_a = 0 for i = [0 len){
if (min_h > height[i]) then continue
min_h = height[i]
for j = [i len){
if (min_h > height[j]){
min_h = height[j]
}
max_a = max(max_a, min_h * (j-i+1))
}
}

这是表达思路的伪码,大概就是,以每个柱子为基点,向前依次遍历其余柱子,用当前最短的那根乘上此刻前进的距离来求得面积,同时更新最大面积。这样遍历下来是O(n^2)的,虽然没有遗漏,但是也有很多不必要的枚举。
代码中 if (min_h > height[i]) then continue 这句是我尝试的一个优化,因为如果此趟遍历的高度都不超过前一趟的最小高度的话,这一趟得到的最大面积绝不会比前一趟大。但是这个优化仍是收效甚微,大集合没有通过。
至此也没有想到其他的优化手段,但是确实有人用优化过的暴力方法通过了大集合测试...我战斗力还是没有突破5啊。

暴力完整代码(Time Limit Exeeded):

 int largestRectangleArea(vector<int>height){
int maxArea=, minHeight=;
for (int i=; i<height.size(); i++){
if(height[i] <= minHeight)continue;
minHeight = height[i];
for (int j=i; j<height.size(); j++){
if (height[j] < minHeight){
minHeight = height[j];
}
int curArea = (j-i+) * minHeight;
if (curArea > maxArea){
maxArea = curArea;
}
}
}
return maxArea;
}

下面看看那个非常聪明流弊的O(n)解,还是建议去看一下开头提到的那篇博客,虽然几个图画的有问题,但是不影响理解的。
首先,他用一个栈来维护一个单调递增序列。 即在遍历过程中,遇到比栈顶大的才push。注意栈里保存的是索引。
如果遇到比栈顶小的,pop出栈顶并以他对应的实际数据为height,乘以一个width,求得面积并更新最大面积。那个width就是当前遍历位置i当前栈顶(注意已经pop过一次)的间距(不包括当前栈顶位置)
这样到遍历完成的时候我们就可以得到最大面积,因为每次弹栈,我们都确保了弹出的那个家伙获得了他组成的最大面积。噢,为了确保最后把栈弹空,我们需要在原数据后面加一个dummy的0。

这是AC的:

 int largestRectangleArea2(vector<int>height){
stack<int> s;
int maxArea = ;
int i=;
height.push_back();//dummy
int len = height.size();
while (i < len){
if (s.empty() || height[s.top()] < height[i]){
s.push(i++);
}else {
int h = s.top();
s.pop();
maxArea = max(maxArea, s.empty()? i*height[h] : height[h] * (i - s.top() - ));
}
}
return maxArea;
}
上一篇:解决报错:import sun.misc.BASE64Decoder无法找到


下一篇:redis 哨兵机制环境搭建