企业官网建设流程全解析

一、题目

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

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

输入： heights = [2,4] 输出： 4 提示： 1 <= heights.length <=105 0 <= heights[i] <= 104

二、思路

第一眼就想到单调栈了，但是一直卡在如何在不pop元素的情况下遍历栈中所有的成员。

但后面发现，在pop元素时结算即可。

思路算是比较经典吧，用栈来存储高度单调递减的下标，当更小的元素进来时，将栈里比他大的挨个pop出去，并结算开区间的面积大小；最后再把自身下标push下标进去。

三、题解

class Solution { public: int largestRectangleArea(vector<int>& heights) { int res=0; stack<int> st; heights.push_back(0); for(int i=0;i<heights.size();i++){ while(!st.empty()&&heights[i]<heights[st.top()]){ int h=st.top(); st.pop(); int left=st.empty()?-1:st.top(); int width=i-1-left; res=max(res,heights[h]*width); } st.push(i); } return res; } };