微软面试题： LeetCode 84. 柱状图中最大的矩形 出现次数：1

 1 //单调栈 时间 O(n)  空间O(n)
 2     int largestRectangleArea(vector<int>& heights)
 3     {
 4         const int len = heights.size();
 5         if(len == 0) return 0;
 6         heights.push_back(0);//哨兵
 7         int res = 0;
 8         std::stack<int> st;//遍历过程中，栈内的元素总是非单调递增的
 9         for(int i = 0; i <= len;++i)//哨兵也要和栈内元素比较，保证循环结束，所有的元素都出栈，栈内只剩下哨兵
10         {
11             if(!st.empty() && heights[i] < heights[st.top()])//当前元素比栈顶元素小
12             {
13                 while(!st.empty() && heights[i] < heights[st.top()])//栈内所有元素大于heights[i]的 都要出栈
14                 {
15                     int tp = heights[st.top()];
16                     while(!st.empty() && heights[st.top()] == tp)//将栈内和栈顶元素相同的全部出栈，根据坐标间距计算矩形的长
17                     {
18                         st.pop();
19                     }
20                     int l = st.empty()?-1:st.top();
21                     res = max(res,tp * (i - l - 1));
22                 } 
23             }
24             st.push(i);
25         }
26         return res;
27     }