84. 柱状图中最大的矩形

1.题目描述

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 求在该柱状图中，能够勾勒出来的矩形的最大面积。 以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。 图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。 示例:

2.思路（单调栈）

单调递增栈操作规则： 1.如果新的元素比栈顶元素大，就入栈 2.如果新的元素较小，那就一直把栈内元素弹出来，直到栈顶比新元素小 3.当元素出栈时，说明这个新元素是出栈元素向后找第一个比其小的元素 此时right = i - 1 4.当元素出栈后，说明新栈顶元素是出栈元素向前找第一个比其小的元素 此时left = s.back() + 1 举例： 栈里是 1 5 6 。 接下来新元素是 2 ，那么 6 需要出栈。 当 6 出栈时，右边 2 代表是 6 右边第一个比 6 小的元素。 当 6 出栈时，5 成为新的栈顶，那么 5 就是 6 左边第一个比 6 小的元素。

3.代码

int largestRectangleArea(vector<int>& heights){ int res = 0; vector<int> s; for(int i = 0;i < heights.size();++i){ while(!s.empty() && heights[s.back()] > heights[i]){ int curr = s.back(); s.pop_back(); int left = s.back() + 1; int right = i - 1; res = max(res, (right - left + 1) * heights[curr]); } s.push_back(i); } return res; }

4.复杂度分析

时间复杂度：O(N)。 空间复杂度：O(N)。