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

[解题思路]
对于每一个height，遍历前面所有的height，求取面积最大值。时间复杂度是O(n*n)

 1: int largestRectangleArea(vector<int> &height) {   
 2:   // Start typing your C/C++ solution below   
 3:   // DO NOT write int main() function   
 4:   //int result[height.size()];   
 5:   int maxV = 0;   
 6:   for(int i =0; i< height.size(); i++)   
 7:   {   
 8:    int minV = height[i];   
 9:    for(int j =i; j>=0; j--)   
 10:    {   
 11:     minV = std::min(minV, height[j]);   
 12:     int area = minV*(i-j+1);   
 13:     if(area > maxV)   
 14:      maxV = area;   
 15:    }   
 16:   }   
 17:   return maxV;   
 18:  }   

可以过小数据，但是大数据超时。可以理解，这个解法包含了很多重复计算。一个简单的改进，是只对合适的右边界（峰顶），往左遍历面积。

 1: int largestRectangleArea(vector<int> &height) {   
 2:   // Start typing your C/C++ solution below   
 3:   // DO NOT write int main() function   
 4:   int maxV = 0;   
 5:   int start = 0;   
 6:   int end = height.size();   
 7:   while(start< height.size())   
 8:   {      
 9:    end = height.size() -1;   
 10:    for(int k = start+1;k <= end; k++)   
 11:    {   
 12:     if(height[k] < height[k-1])   
 13:     {   
 14:      end = k-1;   
 15:      break;   
 16:     }   
 17:    }   
 18:    int minV = height[end];   
 19:    for(int j =end; j>=0; j--)   
 20:    {   
 21:     minV = std::min(minV, height[j]);   
 22:     int area = minV*(end-j+1);   
 23:     if(area > maxV)   
 24:      maxV = area;   
 25:    }   
 26:    start = end +1;   
 27:   }   
 28:   return maxV;   
 29:  }   

这样的话，就可以通过大数据。但是这个优化只是比较有效的剪枝，算法仍然是O(n*n).

O(n)的解法 如下图所示，从左到右处理直方，i=4时，小于当前栈顶（及直方3），于是在统计完区间[2,3]的最大值以后，消除掉阴影部分，然后把红线部分作为一个大直方插入。因为，无论后面还是前面的直方，都不可能得到比目前栈顶元素更高的高度了。

这就意味着，可以维护一个递增的栈，每次比较栈顶与当前元素。如果当前元素小于栈顶元素，则入站，否则合并现有栈，直至栈顶元素小于当前元素。结尾入站元素0，重复合并一次。

思路很巧妙，代码如下, 大数据 76ms过。

 1:   int largestRectangleArea(vector<int> &height) {   
 2:   // Start typing your C/C++ solution below   
 3:   // DO NOT write int main() function   
 4:   int stack[height.size()+1], width[height.size()+1];   
 5:   if(height.size() == 0) return 0;   
 6:   int top = 0, area = INT_MIN;   
 7:   stack[0] = 0;   
 8:   width[0] = 0;   
 9:   int newHeight;   
 10:   for(int i =0; i<= height.size(); i++)   
 11:   {   
 12:    if(i < height.size()) newHeight = height[i];   
 13:    else newHeight = -1;   
 14:    if(newHeight>= stack[top])   
 15:    {   
 16:      stack[++top] = newHeight;   
 17:      width[top] = 1;   
 18:    }   
 19:    else   
 20:    {   
 21:      int minV = INT_MAX;   
 22:      int wid= 0;   
 23:      while(stack[top] > newHeight)   
 24:      {   
 25:        minV = min(minV, stack[top]);   
 26:        wid += width[top];   
 27:        area = max(area, minV*(wid));   
 28:        top--;   
 29:       }   
 30:       stack[++top] = newHeight;   
 31:       width[top] = wid+1;   
 32:     }   
 33:   }   
 34:   return area;      
 35:  }   

引入stack后的解法可以优化成如下：

 1: int largestRectangleArea(vector<int> &h) {   
 2:    stack<int> S;   
 3:    h.push_back(0);   
 4:    int sum = 0;   
 5:    for (int i = 0; i < h.size(); i++) {   
 6:      if (S.empty() || h[i] > h[S.top()]) S.push(i);   
 7:      else {   
 8:         int tmp = S.top();   
 9:         S.pop();   
 10:         sum = max(sum, h[tmp]*(S.empty()? i : i-S.top()-1));   
 11:         i--;   
 12:      }   
 13:    }   
 14:    return sum;   
 15: }   

[总结]
这道题的解法引入的stack非常巧妙，利用了space减少重复计算的问题。space O(n), time O(n)