由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 这个histgram的最大面积问题
相关主题
Largest Rectangle in Histogram不同算法的复杂度能在这里问个算法题目么?
challenge: 找bug问一个题
LC装水容器题一定要O(nlogn)做法吗?总结一道题
有用java过Maximal Rectangle的judge large的吗?弱弱的问:最大长方形in histogram 和 直方图下雨有关系吗?
我也来问问LC的Maximal RectangleGoogle的电话面试题
求“bar组成的histogram求最大内切矩形”的link...Amazon coding question
Largest Rectangle in Histogram一些算法题。
google的一道题求解题目: iterative binary tree post order traversal
相关话题的讨论汇总
话题: item话题: maxarea话题: stack话题: histogram话题: value
进入JobHunting版参与讨论
1 (共1页)
h*****y
发帖数: 218
1
在网上发现这个最大直方图求面积的题目的解答,有一个地方没看明白
http://www.sureinterview.com/shwqst/1117001
下面这个代码的stack为什么有一个get的方法?
if (prev.height > stk.get(stk.size() - 2).height) {
======================================================================
public long getMaxArea(int[] histogram) {
long maxArea = 0;
if (histogram == null || histogram.length == 0)
return maxArea;
Stack stk = new Stack();
stk.push(new Item(Integer.MIN_VALUE, -1));
for (int i = 0; i <= histogram.length; i++) {
Item cur = new Item((i < histogram.length ? histogram[i]
: Integer.MIN_VALUE), i);
if (cur.height > stk.peek().height) {
stk.push(cur);
continue;
}
while (stk.size() > 1) {
Item prev = stk.peek();
long area = (i - prev.pos) * prev.height;
if (area > maxArea) {
maxArea = area;
}
prev.height = cur.height;
if (prev.height > stk.get(stk.size() - 2).height) {
break;
}
stk.pop();
}
}
return maxArea;
}
1 (共1页)
进入JobHunting版参与讨论
相关主题
题目: iterative binary tree post order traversal我也来问问LC的Maximal Rectangle
O(NlogN) largest rectangle in histogram求“bar组成的histogram求最大内切矩形”的link...
G面经Largest Rectangle in Histogram
leetcode一道题google的一道题求解
Largest Rectangle in Histogram不同算法的复杂度能在这里问个算法题目么?
challenge: 找bug问一个题
LC装水容器题一定要O(nlogn)做法吗?总结一道题
有用java过Maximal Rectangle的judge large的吗?弱弱的问:最大长方形in histogram 和 直方图下雨有关系吗?
相关话题的讨论汇总
话题: item话题: maxarea话题: stack话题: histogram话题: value