做网站怎么打不开localhost,搭建网站一条龙,门户网站主要特点和功能,宁夏正丰建设集团公司联网站84 柱状图中最大的矩形
题目链接#xff1a;84. 柱状图中最大的矩形 - 力扣#xff08;LeetCode#xff09;
给定 n 个非负整数#xff0c;用来表示柱状图中各个柱子的高度。每个柱子彼此相邻#xff0c;且宽度为 1 。
求在该柱状图中#xff0c;能够勾勒出来的矩形的…84 柱状图中最大的矩形
题目链接84. 柱状图中最大的矩形 - 力扣LeetCode
给定 n 个非负整数用来表示柱状图中各个柱子的高度。每个柱子彼此相邻且宽度为 1 。
求在该柱状图中能够勾勒出来的矩形的最大面积。
输入heights [2,1,5,6,2,3]
输出10
解释最大的矩形为图中红色区域面积为 10思路使用left、right分别记录每个元素左边比它小和右边比它小的位置。
class Solution {
public:int largestRectangleArea(vectorint heights) {vectorint left(heights.size(), -1);vectorint right(heights.size(), heights.size());stackint 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;}
};
