5/30刷题

1.柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
示例:
输入: [2,1,5,6,2,3]
输出: 10

思路：单调栈：利用一个单调递增栈来寻找第i个柱子左面和右面第一个小于它的柱子。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
     //利用单调递增栈的思想https://blog.csdn.net/Zolewit/article/details/88863970
     heights.push_back(0);//最右面添加一个最小元素
     stack<int> stk;
     int maxArea = 0;
     for(int i = 0;i<heights.size();i++)
     {
         while(!stk.empty() && heights[i]<heights[stk.top()])
         {
             //如果出现小于栈顶元素的元素，就将栈顶元素出栈，此时的原栈顶元素右面第一个小于它的柱子下标是i
             //原栈顶元素左面第一个小于它的柱子下标是新栈顶元素
             int top= stk.top();
             stk.pop();
             maxArea = max(maxArea,heights[top]*(stk.empty()? i:(i - stk.top() -1)));
         }
         stk.push(i);
     }
     return maxArea;     
    }
};