lc84 往左往右扩展

2016-08-07  本文已影响42人  Isabella10

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[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;
            }
        }
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


小收获

  1. 记忆化的思想,不仅仅和DP有关
    对于严格的DP来说,是用前面已知的来推导出接下来出现的,但是记忆化的思想不仅仅体现在DP上。

有些时候,如果算法中有往前(搜索\扩展\移动)
或者往后(搜索\扩展\移动)
已知的记录,或许可以用来帮我们加速某种向前(或者向后)搜索的过程
把 ** j-- 变成 j-step[某] **
把 ** j++ 变成 j+step[某] **

  1. stack

参考:
http://www.cnblogs.com/boring09/p/4231906.html (Specail thans to u~)

上一篇 下一篇

猜你喜欢

热点阅读