柱状图中最大的矩形

 1int largestRectangleArea(vector<int>& heights)
 2{
 3    // 当右边所有矩形都比当前矩形高时
 4    // 有可能不会计算以当前矩形为中心的结果
 5    // 在末尾设置一个 -1（比任何矩形都要低）
 6    // 可以强制触发”heights[right] <= heights[st.top()]“
 7    // 计算当前结果
 8    heights.push_back(-1);
 9    std::stack<int> st;
10    // 同理，这里是为了防止左边都高于右边的情况
11    st.push(-1);
12    int area = 0;
13
14    // 外层循环会对每一个矩形都进行一次 area 的计算
15    for(int right = 0; right < heights.size(); right++)
16    {
17        // 内层循环则定义具体的计算步骤
18        while(1 < st.size() && heights[right] <= heights[st.top()])
19        {
20            // 栈顶代表矩形的高
21            int h = st.top();
22            st.pop();
23            // 栈顶下面的那个数代表左边界
24            int left = st.top();
25            // 计算面积
26            area = std::max(area, heights[h] * (right - left - 1));
27        }
28        // 将当前的右边界作为下一次的左边界
29        st.push(right);
30    }
31    return area;
32}