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)

[Code]

1:  int largestRectangleArea(vector
    
      &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
    
      &height) {   2:       int maxV = 0;   3:       for(int i =0; i< height.size(); i++)  4:       {  5:            if(i+1 < height.size()   6:                      && height[i] <= height[i+1]) // if not peak node, skip it  7:                 continue;  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:  }
    

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

想了半天，也想不出来O(n)的解法，于是上网google了一下。

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

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

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

1:     int largestRectangleArea(vector
    
      &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的做法相当巧妙。

Update: Refactor code 5/7/2013

评论中Zhongwen Ying的code写的比我post的code简洁多了。把他的code format一下集成进来。

1:  int largestRectangleArea(vector
    
      &h) {  2:       stack
     
       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:  }