Largest Rectangle in Histogram
程序员文章站
2022-06-17 22:54:47
...
1,题目要求
Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
给定n个非负整数表示直方图的条形高度,其中每个条形的宽度为1,找到直方图中最大矩形的区域。
2,题目思路
对于这道题,是求出一个直方图中可以找到的最大的矩形面积。
在一个直方图中,对于第i个柱子,由它往左右扩展的最大的矩形的宽度为:right - left -1
其中:
- left:在i的左侧第一个比其矮的柱子的下标
- right:在i的右侧第一个比其矮的柱子的下标
由题目中的例子我们有:
对于柱子6,左边第一个比它矮的,自然是5,下标为2
而右边第一个比它矮的,则是2,下标位4
于是,以柱子6出发的最大矩形,高度为6,长度为4-2-1 = 1
再比如,对于柱子5,左边第一个比它矮的,是1,下标为1
右边第一个比它矮的,则是2,下标为4
于是,以柱子5出发的最大矩形,高度为5,长度为4-1-1 = 2
符合事实。
算法具体实现逻辑见代码注释部分。
3,代码实现
static const auto s = []() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
return nullptr;
}();
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int maxArea = 0;
heights.push_back(0); //在末尾虚构一个高度为0的柱子,用于对总的情况的检查
vector<int> index;
for(int i = 0;i<heights.size();i++){
//i说明当前i位置之前有柱子(只有第一个柱子才会有size为0),
//并且,当前柱子的高度比其哪一个柱子矮,
//说明前面柱子所能达到的最大值已经可以尝试计算了
while(index.size()!=0 && heights[index.back()] >= heights[i]){
//取当前最高的(最后一个)柱子的高度来计算最大面积
//之所以是合理的,是因为我们在加入柱子的索引到index时
//一定是按照柱子高度从低到高加入的
//如果遇到两柱子相邻却变矮,则一定会进入while来计算这个面积
int currH = heights[index.back()];
index.pop_back(); //获得高度之后,删除当前最高柱子的索引
//获得刚才最高的柱子前面一个柱子、
//也即当前所有柱子里面最高的柱子的索引
//即可以构成的、合法的举矩形的前一个位置
//就是刚才最高柱子左侧最近的较矮柱子的下标
//对于第一个柱子,我们需要单独判断, 并设置-1作为虚拟的、0的前一个位置
//为了方便理解,定义右侧最近的比当前柱子矮的下标
int rightLowerIdx = i;
int leftLowerIdx = index.size() == 0? -1 : index.back();
maxArea = max(maxArea, currH * (rightLowerIdx - leftLowerIdx - 1));
}
//将当前的下标加入
index.push_back(i);
}
return maxArea;
}
};
上一篇: Largest Rectangle in Histogram
下一篇: 程序员表白代码(一)
推荐阅读
-
【题解】hdu1506 Largest Rectangle in a Histogram
-
教你利用Python玩转histogram直方图的五种方法
-
[Trie] The XOR Largest Pair
-
2019牛客暑期多校训练营(第二场)H Second Large Rectangle
-
The XOR Largest Pair(tire树)
-
Problem 8: Largest product in a series
-
Find the largest open file through lsof
-
Leetcode 391. Perfect Rectangle
-
5. Kth Largest Element
-
Largest Submatrix (最大全1子矩阵)