台州建设局网站信息价成都网站建设麦格思

84 柱状图中最大的矩形

题目链接：84. 柱状图中最大的矩形 - 力扣（LeetCode）

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

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

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

思路：使用left、right分别记录每个元素左边比它小和右边比它小的位置。

class Solution {
public:int largestRectangleArea(vector<int>& heights) {vector<int> left(heights.size(), -1);vector<int> right(heights.size(), heights.size());stack<int> s;int result = 0;//rightfor(int i = 0; i < heights.size(); i++){while(!s.empty() && heights[i] < heights[s.top()]){right[s.top()] = i;s.pop();}s.push(i);}while(!s.empty()) { s.pop();}//leftfor(int i = heights.size() - 1; i >= 0; i--){while(!s.empty() && heights[i] < heights[s.top()]){left[s.top()] = i;s.pop();}s.push(i);}for(int i = 0; i < heights.size(); i++){result = max(result, (right[i] - left[i] - 1) * heights[i]);}return result;}
};