Largest Rectangle in Histogram
程序员文章站
2022-06-17 22:54:53
...
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.
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3]
.
The largest rectangle is shown in the shaded area, which has area = 10
unit.
For example,
Given height = [2,1,5,6,2,3]
,
return 10
.
遍历数组,每找到一个局部峰值,然后向前遍历所有的值,算出共同的矩形面积,每次对比保留最大值,代码如下:
// Pruning optimize
class Solution {
public:
int largestRectangleArea(vector<int> &height) {
int res = 0;
for (int i = 0; i < height.size(); ++i) {
if (i + 1 < height.size() && height[i] <= height[i + 1]) {
continue;
}
int minH = height[i];
for (int j = i; j >= 0; --j) {
minH = min(minH, height[j]);
int area = minH * (i - j + 1);
res = max(res, area);
}
}
return res;
}
};
也可用栈来维护一个高度递增序列,每次遇到较小的高度就开始计算矩形面积,代码如下
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int res = 0;
stack<int> st;
heights.push_back(0);
for (int i = 0; i < heights.size(); ++i) {
while (!st.empty() && heights[st.top()] >= heights[i]) {
int cur = st.top(); st.pop();
res = max(res, heights[cur] * (st.empty() ? i : (i - st.top() - 1)));
}
st.push(i);
}
return res;
}
};
推荐阅读
-
OpenCV-Python 绘制矩形,绘制文本,获取文本大小【rectangle(),getTextSize(),putText()】
-
【题解】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