[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.

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.

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;

 }

巴特西

[LeetCode] Largest Rectangle in Histogram

最新文章

热门文章