lc84 往左往右扩展

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

---

小收获

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

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

2. stack

---

参考：
http://www.cnblogs.com/boring09/p/4231906.html （Specail thans to u~）