Problem description:
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.

Example:

1
2
Input: [2,1,5,6,2,3]
Output: 10

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int largestRectangleArea(vector<int>& height) {            
        int ret = 0;
        height.push_back(0);
        vector<int> index;
        for(auto n: height)
            cout<<n<<endl;
            
        for(int i = 0; i < height.size(); i++)
        {
            cout<< "i: "<<i<<endl;
            if(i == 4) cout<<index.size()<<endl;
            while(index.size() > 0 && height[index.back()] >= height[i])
            {
                int h = height[index.back()];
                cout<< "h:" <<h;
                index.pop_back();
                
                int sidx = index.size() > 0 ? index.back() : -1;
                cout<< ", sidx:" <<sidx;
                if(h * (i-sidx-1) > ret)
                    ret = h * (i-sidx-1);
                cout<< ", calculate:" <<h * (i-sidx-1)<<endl;
            }
            cout<< "ret: "<<ret<<endl;
            index.push_back(i);
        }
        
        return ret;
    }
};

Second time

This is a relatively straightforward solution. Use a pointer to find toward right, if a histogram i is greater than i+1, then we find a left boundary of this histogram i. At this time, we traverse back toward left, find every minimum height and multiply with the width to get the area.
指針往右遍歷, 當height[i]< height[i+1]: keep go right, 因如果後面比較高, 則maximum area 至少包含後面的 histogram.

example:
[2,4,6,5,3]

  1. reach 6, next is 5.
    minimum height* width= area
    6*1= 6
4*2= 8
2*3= 6
  2. reach 5, next is 3, smaller than 5.
    5*1= 5
5*2= 10
4*3= 12
2*4= 8
  3. reach 3, end condition
    3*1= 3
3*2= 6
3*3= 9
3*4= 12
2*5= 10
  4. max area is 12

#Solution:

    //O(n^2)
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int res= 0;
        for(int i= 0; i< heights.size(); i++){ //go toward left
            if(i== heights.size()-1 || heights[i]> heights[i+1]){ //reached end || height[i]> heigh[i+1]
                int minh= heights[i];
                for(int j= i; j>=0; j--){ //go toward right, find every rectangle
                    minh= min(minh, heights[j]);
                    int area= minh* (i-j+1);
                    res= max(res, area);
                }
            }
        }
        return res;
    }
};

Reference:
https://goo.gl/JusVW4
leetcode.com/problems/maximal-rectangle/discuss/29054/Share-my-DP-solution/27983