84. Largest Rectangle in Histogram

The idea is to keep tracking the increasing rectangles (i.e. keep pushing increasing rectangles into stack) until one rectangle stops increasing (i.e. heights[i] <= heights[i-1]). At that point, we calculate the area. We'll pop out the rectangles that breaks the increasing sequence until a new increasing sequence including heights[i] is formed again. And then we'll start scanning next rectangle in the input again.
With regard to computing area, my initial thinking is the new area will be heights[stack.top] * (i - stack.top). However, this is wrong because this formula doesn't count the situation where the stack becomes empty. Note the stack keeps increasing rectangles so when it becomes empty, it means all the rectangle before the last one in the stack are higher than it. so the area should be heights[last stack element] * i.

1:  class Solution {  
2:  public:  
3:    int largestRectangleArea(vector<int>& heights) {  
4:      heights.push_back(0);  
5:      stack<int> stk;  
6:      int area = 0;  
7:      int height = 0, width = 0;  
8:      for (int i = 0; i < heights.size(); i++) {  
9:        while (!stk.empty() && heights[stk.top()] >= heights[i]) {  
10:          height = heights[stk.top()];  
11:          stk.pop();  
12:          width = stk.empty() ? i : i-stk.top()-1;  
13:          area = max(area, height*width);  
14:        }  
15:        stk.push(i);  
16:      }  
17:      return area;  
18:    }  
19:  };