Maximum Rectangle in Histogram

来源：Twitter Phone Interview，Leetcode

原帖：https://leetcode.com/problems/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.

思路：
Twitter first round phone interview。使用stack保存栈内递增序列，原数组需要加入一个最小值-1，保持栈内元素能够完全清空。

代码：

 class Solution {  
 public:  
     //stack keeps increasing/decreasing order numbers.   
     //for example: 2 1 8 9 4 5 3   
     //寻找i左侧比A[i]大的第一个数  
     int largestRectangleArea(vector<int> &height) {  
         if (height.empty()) return 0;  
         stack<int> s;  
         height.push_back(-1); //辅助空间，帮助把栈内所有元素pop  
         int maxRect = 0;  
         int i = 0, size = height.size();  
         while (i < size) {  
             if (s.empty() || height[s.top()] <= height[i]) { // left search  
                 s.push(i++);  
             } else { // right search  
                 int h = height[s.top()]; s.pop(); // stk.top()保存可以作为矩形顶点的最大高度, then s.pop()  
                 int w = s.empty() ? i : i - s.top() - 1; // s.top() is left boundary; i is right boundary  
                 maxRect = max(maxRect, w * h);  
             }  
         }  
         return maxRect;  
     }  
 };