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

给定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

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