Largest Rectangle in Histogram
程序员文章站
2022-06-17 22:50:17
...
题目
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.
答案
每次看到更高的height的时候,就把它放进stack里
遇到比stack.top()小的height时,则开始pop stack,计算rectangle的面积
直到iterate完整个heights数组,以及stack里也为空时则完成
public int largestRectangleArea(int[] heights) {
Stack<Integer> pos = new Stack<>();
Stack<Integer> h = new Stack<>();
int max_area = 0;
for(int i = 0; i < heights.length; i++) {
int curr_h = heights[i];
if(h.empty() || curr_h > h.peek()) {
h.push(curr_h);
pos.push(i);
}
int last_h = h.peek();
int last_pos = pos.peek();
if(curr_h < last_h) {
int idx = 0, hs = 0;
while(!h.empty() && h.peek() > curr_h) {
idx = pos.pop();
hs = h.pop();
max_area = Math.max(max_area, hs * (i - idx));
}
h.push(curr_h);
pos.push(idx);
}
}
while(!h.empty()) {
max_area = Math.max(max_area, h.pop() * (heights.length - pos.pop()));
}
return max_area;
}
推荐阅读
-
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