leetcode 84. 柱状图中最大的矩形

84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：

输入： heights = [2,4]
输出： 4

思路：

        /*

            单调递减栈

            遍历到的数组元素大于或等于栈顶元素，压入栈

            遍历到的数组元素小于栈顶元素，取出栈顶元素为middle,st.pop(),heights[i] = right; left = st.top();

            h = height[middle];

            w = i-st.top()-1;

            遍历到的数组元素小于栈顶元素的判断是持续性的判断

            result = max(h*w,result);

        */

代码：

class Solution {
public:int largestRectangleArea(vector<int>& heights) {/*单调递减栈遍历到的数组元素大于或等于栈顶元素，压入栈遍历到的数组元素小于栈顶元素，取出栈顶元素为middle,st.pop(),heights[i] = right; left = st.top();h = height[middle];w = i-st.top()-1;遍历到的数组元素小于栈顶元素的判断是持续性的判断result = max(h*w,result); */int result = 0;stack<int>st;st.push(0);heights.insert(heights.begin(),0);heights.push_back(0);for(int i = 1;i<heights.size();i++){if(heights[i]>heights[st.top()]){st.push(i);}else if(heights[i]==heights[st.top()]){st.push(i);}else{while(!st.empty()&&heights[i]<heights[st.top()]){int middle = st.top();st.pop();if(!st.empty()){int right = i;int left = st.top();int h = heights[middle];int w = right-left-1;result = max(result,h*w);}}}st.push(i);}return result;}
};

还有很多瑕疵，还需继续坚持！