leetcode 84. 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.
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3]
The largest rectangle is shown in the shaded area, which has area = 10 unit.
思路
- 因为是“水桶模型”,所以在某一个解中,一定会有所谓的“短板”
- 如果对于当前的每一个位置,其实可以往左往右扩展,直到面积变小了。
策略
方法一 用数组
- 用一个left数组,记录当前位置向左扩展,最多能够扩展的格子数(包括当前矩形自身)
举个栗子:
// 对于当前的高度,最多能往左边扩展多少(包括当前)
left[0] = 1;
for(int i=1; i<len; i++)
{
if(heights[i] > heights[i-1])
left[i] = 1;
else
{
int j = i-1;
while( j>=0 && heights[j] > heights[i])
j--;
left[i] = i-j;
}
}
- 用一个right数组,记录当前位置向右扩展,最多能够扩展的格子数(包括当前矩形自身)
- 用一个area数据,记录从当前位置开始,往左往右扩展,最多能扩展的格子数。
ans = Math.max( heights[i] * (right[i] + left[i] - 1), ans);
优化点
既然是扩展,那么能不能利用已知的,来加速呢?
记忆化加速“移动” :
举个栗子,在找往左扩展的过程中,left记录的是当下位置能往左扩展(跳)多少格
假设有 A B C D 四个位置,C可以往左扩展(跳)到 A,
那么,如果D可以扩展到C,D自然也可以扩展到A,
因此没有必要 j--, 而可以直接减去left记录的C的对应扩展数。
具体代码见leetcode
方法二 用stack
参考:
http://www.makuiyu.cn/2015/03/LeetCode_84.%20Largest%20Rectangle%20in%20Histogram/
http://www.cnblogs.com/boring09/p/4231906.html
小收获
-
记忆化的思想,不仅仅和DP有关
对于严格的DP来说,是用前面已知的来推导出接下来出现的,但是记忆化的思想不仅仅体现在DP上。
有些时候,如果算法中有往前(搜索\扩展\移动)
或者往后(搜索\扩展\移动)
已知的记录,或许可以用来帮我们加速某种向前(或者向后)搜索的过程,
把 ** j-- 变成 j-step[某] **
把 ** j++ 变成 j+step[某] **
- stack
参考:
http://www.cnblogs.com/boring09/p/4231906.html (Specail thans to u~)