由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - largest rectangle in histogram
相关主题
也发个A家电面经总结一道题
想贴一个我收集的算法高频题的博客不知道有没有人看请问一道题--给一个正方形矩阵,每个元素要么黑色要么白色,请找出最大的纯色子矩阵
【非死不可面经】今天FB面试onsite,求blessO(NlogN) largest rectangle in histogram
请教大家一道Google的题目那个常见的histogram max rectangle 问题
做了一下Kth small in young tablet 和 largest rectangle contain 1s又想起一道google题目
罗马转数字,数字转罗马问题maximum rectangle in histogram 到底是个什么问题?
Google interview questionchallenge: 找bug
google 面试题histogram问题
相关话题的讨论汇总
话题: int话题: nminindex话题: max话题: stack
进入JobHunting版参与讨论
1 (共1页)
m*******1
发帖数: 77
1
这个题看了不少的讲解,大概就是维护一个栈,每当找到一个右边界时,弹出所有的左
边界进行计算,但是不明白为什么是O(n),因为我觉得有些元素会不止一次的做左边界
,leetcode上的一个测试例子是:
3,6,5,7,4,8,1,0
最大面积是4*5 = 20,但是当8作为右边界开始弹出时,6已经弹出,这样的话如何得到
左边界呢?
s*********s
发帖数: 140
2
我看到的一种解法是用stack存短的bar,而不是存边界。http://tech-queries.blogspot.com/2011/03/maximum-area-rectangle-in-histogram.html
s*********s
发帖数: 140
3
我觉得就像http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html 里面说的,stack存的是started but yet unfinished subhistograms. 而且stack存的是高度的index,不是高度本身。你要是只存高度,那宽度的信息就丢失了。比如在你要得到4*5=20这个结果的时候,应该是iterate到了1,在将要弹出4的高度的时候,此时的stack应该是[3的index:0] -> [4的index:4]. 那rectangle的宽度是根据3的index0和1的index6来算的,就是6-0 - 1 = 5.
l*******b
发帖数: 2586
4
终于会做了。。。
int largestRectArea(vector &h) {
stack p;
int i = 0, m = 0;
h.push_back(0);
while(i < h.size()) {
if(p.empty() || h[p.top()] <= h[i])
p.push(i++);
else {
int t = p.top();
p.pop();
m = max(m, h[t] * (p.empty() ? i : i - p.top() - 1 ));
}
}
return m;
}
p*****2
发帖数: 21240
5

这个不错,过了OJ了?一会儿学习一下。

【在 l*******b 的大作中提到】
: 终于会做了。。。
: int largestRectArea(vector &h) {
: stack p;
: int i = 0, m = 0;
: h.push_back(0);
: while(i < h.size()) {
: if(p.empty() || h[p.top()] <= h[i])
: p.push(i++);
: else {
: int t = p.top();

l*******b
发帖数: 2586
6
过了,哈哈

【在 p*****2 的大作中提到】
:
: 这个不错,过了OJ了?一会儿学习一下。

p*****2
发帖数: 21240
7

上来加个0有点tricky呀。如果给定是int[]就不能那么做了。

【在 l*******b 的大作中提到】
: 过了,哈哈
c*****a
发帖数: 808
8

不用0和int[]的话,最后加上这些就可以啦
while(!stack.empty):
m = max(m,h[stack.pop]* (stack.empty() ? i : i-stack.peek()-1))

【在 p*****2 的大作中提到】
:
: 上来加个0有点tricky呀。如果给定是int[]就不能那么做了。

l*******b
发帖数: 2586
9
嗯,对的,本来想着还得给while里加好几句,所以才给h里push了个0,强制把stack都
弹出来

【在 c*****a 的大作中提到】
:
: 不用0和int[]的话,最后加上这些就可以啦
: while(!stack.empty):
: m = max(m,h[stack.pop]* (stack.empty() ? i : i-stack.peek()-1))

p*****2
发帖数: 21240
10

我的意思是这个trick挺好,但是面试的时候很可能用不上。

【在 c*****a 的大作中提到】
:
: 不用0和int[]的话,最后加上这些就可以啦
: while(!stack.empty):
: m = max(m,h[stack.pop]* (stack.empty() ? i : i-stack.peek()-1))

相关主题
罗马转数字,数字转罗马问题总结一道题
Google interview question请问一道题--给一个正方形矩阵,每个元素要么黑色要么白色,请找出最大的纯色子矩阵
google 面试题O(NlogN) largest rectangle in histogram
进入JobHunting版参与讨论
p*****2
发帖数: 21240
11
不过我觉得这题是我做的所有面试题里差不多最难的。自己根本不可能想出来。
d*****9
发帖数: 90
12
这个和那个山上存雨水的问题有共通之处吧?
k****r
发帖数: 807
13
lz,测8的时候,4就已经是他的左边界了。

【在 m*******1 的大作中提到】
: 这个题看了不少的讲解,大概就是维护一个栈,每当找到一个右边界时,弹出所有的左
: 边界进行计算,但是不明白为什么是O(n),因为我觉得有些元素会不止一次的做左边界
: ,leetcode上的一个测试例子是:
: 3,6,5,7,4,8,1,0
: 最大面积是4*5 = 20,但是当8作为右边界开始弹出时,6已经弹出,这样的话如何得到
: 左边界呢?

k****r
发帖数: 807
14
那个能装多少水的那个,我脚的比这个还难呢

【在 p*****2 的大作中提到】
: 不过我觉得这题是我做的所有面试题里差不多最难的。自己根本不可能想出来。
b*****n
发帖数: 482
15
这个真是太简洁了。
今天晚上从有思路到AC,吭哧吭哧花了40分钟,一看二爷给了5分的难度,还挺高兴的
。到这儿一看“菜鸟”的code,才是我的1/3,膜拜。 orz

【在 l*******b 的大作中提到】
: 终于会做了。。。
: int largestRectArea(vector &h) {
: stack p;
: int i = 0, m = 0;
: h.push_back(0);
: while(i < h.size()) {
: if(p.empty() || h[p.top()] <= h[i])
: p.push(i++);
: else {
: int t = p.top();

p*****2
发帖数: 21240
16

装水那个我挺快想出来了。这个没想出来当时。

【在 k****r 的大作中提到】
: 那个能装多少水的那个,我脚的比这个还难呢
b*****n
发帖数: 482
17
装水那个我差了一口气,我左右两个index同时移动了。

【在 p*****2 的大作中提到】
:
: 装水那个我挺快想出来了。这个没想出来当时。

w****x
发帖数: 2483
18

//a binary search solution
int GetBiggestRectBin(int a[], int n)
{
if (n <= 0) return 0;
assert(a);
int nMinIndex = 0;
for (int i = 1; i < n; i++)
if (a[nMinIndex] > a[i])
nMinIndex = i;

int nCur = a[nMinIndex] * n;
int nLft = GetBiggestRectBin(a, nMinIndex);
int nRgt = GetBiggestRectBin(a + nMinIndex + 1, n - 1 -nMinIndex);
return max(nCur, max(nLft, nRgt));
}

【在 l*******b 的大作中提到】
: 终于会做了。。。
: int largestRectArea(vector &h) {
: stack p;
: int i = 0, m = 0;
: h.push_back(0);
: while(i < h.size()) {
: if(p.empty() || h[p.top()] <= h[i])
: p.push(i++);
: else {
: int t = p.top();

p*****2
发帖数: 21240
19

这个我当时想到了。不过复杂度高了些。

【在 w****x 的大作中提到】
:
: //a binary search solution
: int GetBiggestRectBin(int a[], int n)
: {
: if (n <= 0) return 0;
: assert(a);
: int nMinIndex = 0;
: for (int i = 1; i < n; i++)
: if (a[nMinIndex] > a[i])
: nMinIndex = i;

w****x
发帖数: 2483
20

我觉得这题真要问的话给个二分就差不多了,又好写。
基本上写堆栈的感觉肯定是见过了

【在 p*****2 的大作中提到】
:
: 这个我当时想到了。不过复杂度高了些。

相关主题
那个常见的histogram max rectangle 问题challenge: 找bug
又想起一道google题目histogram问题
maximum rectangle in histogram 到底是个什么问题?google的一道题求解
进入JobHunting版参与讨论
p*****2
发帖数: 21240
21
我也这么认为

【在 w****x 的大作中提到】
:
: 我觉得这题真要问的话给个二分就差不多了,又好写。
: 基本上写堆栈的感觉肯定是见过了

c********t
发帖数: 5706
22
这道题我想到的是二分法
存水题也很难想,我试图用两边夹,还是没想出,最后想了一个先找出最大数,然后左
右算分别存水量。

【在 b*****n 的大作中提到】
: 装水那个我差了一口气,我左右两个index同时移动了。
w****x
发帖数: 2483
23

其实这题的O(n)解法和那个移动窗口和直方图蓄水问题很类似,都是保证一个递增或递
减序列然后通过index判断距离。

【在 c********t 的大作中提到】
: 这道题我想到的是二分法
: 存水题也很难想,我试图用两边夹,还是没想出,最后想了一个先找出最大数,然后左
: 右算分别存水量。

c********t
发帖数: 5706
24
嗯,我再复习一下体会体会

【在 w****x 的大作中提到】
:
: 其实这题的O(n)解法和那个移动窗口和直方图蓄水问题很类似,都是保证一个递增或递
: 减序列然后通过index判断距离。

m*******1
发帖数: 77
25
这个题看了不少的讲解,大概就是维护一个栈,每当找到一个右边界时,弹出所有的左
边界进行计算,但是不明白为什么是O(n),因为我觉得有些元素会不止一次的做左边界
,leetcode上的一个测试例子是:
3,6,5,7,4,8,1,0
最大面积是4*5 = 20,但是当8作为右边界开始弹出时,6已经弹出,这样的话如何得到
左边界呢?
s*********s
发帖数: 140
26
我觉得就像http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html 里面说的,stack存的是started but yet unfinished subhistograms. 而且stack存的是高度的index,不是高度本身。你要是只存高度,那宽度的信息就丢失了。比如在你要得到4*5=20这个结果的时候,应该是iterate到了1,在将要弹出4的高度的时候,此时的stack应该是[3的index:0] -> [4的index:4]. 那rectangle的宽度是根据3的index0和1的index6来算的,就是6-0 - 1 = 5.
l*******b
发帖数: 2586
27
终于会做了。。。
int largestRectArea(vector &h) {
stack p;
int i = 0, m = 0;
h.push_back(0);
while(i < h.size()) {
if(p.empty() || h[p.top()] <= h[i])
p.push(i++);
else {
int t = p.top();
p.pop();
m = max(m, h[t] * (p.empty() ? i : i - p.top() - 1 ));
}
}
return m;
}
p*****2
发帖数: 21240
28

这个不错,过了OJ了?一会儿学习一下。

【在 l*******b 的大作中提到】
: 终于会做了。。。
: int largestRectArea(vector &h) {
: stack p;
: int i = 0, m = 0;
: h.push_back(0);
: while(i < h.size()) {
: if(p.empty() || h[p.top()] <= h[i])
: p.push(i++);
: else {
: int t = p.top();

l*******b
发帖数: 2586
29
过了,哈哈

【在 p*****2 的大作中提到】
:
: 这个不错,过了OJ了?一会儿学习一下。

p*****2
发帖数: 21240
30

上来加个0有点tricky呀。如果给定是int[]就不能那么做了。

【在 l*******b 的大作中提到】
: 过了,哈哈
相关主题
问个largest rectangle in histogram的问题想贴一个我收集的算法高频题的博客不知道有没有人看
DP算法占用的空间【非死不可面经】今天FB面试onsite,求bless
也发个A家电面经请教大家一道Google的题目
进入JobHunting版参与讨论
c*****a
发帖数: 808
31

不用0和int[]的话,最后加上这些就可以啦
while(!stack.empty):
m = max(m,h[stack.pop]* (stack.empty() ? i : i-stack.peek()-1))

【在 p*****2 的大作中提到】
:
: 上来加个0有点tricky呀。如果给定是int[]就不能那么做了。

l*******b
发帖数: 2586
32
嗯,对的,本来想着还得给while里加好几句,所以才给h里push了个0,强制把stack都
弹出来

【在 c*****a 的大作中提到】
:
: 不用0和int[]的话,最后加上这些就可以啦
: while(!stack.empty):
: m = max(m,h[stack.pop]* (stack.empty() ? i : i-stack.peek()-1))

p*****2
发帖数: 21240
33

我的意思是这个trick挺好,但是面试的时候很可能用不上。

【在 c*****a 的大作中提到】
:
: 不用0和int[]的话,最后加上这些就可以啦
: while(!stack.empty):
: m = max(m,h[stack.pop]* (stack.empty() ? i : i-stack.peek()-1))

p*****2
发帖数: 21240
34
不过我觉得这题是我做的所有面试题里差不多最难的。自己根本不可能想出来。
d*****9
发帖数: 90
35
这个和那个山上存雨水的问题有共通之处吧?
k****r
发帖数: 807
36
lz,测8的时候,4就已经是他的左边界了。

【在 m*******1 的大作中提到】
: 这个题看了不少的讲解,大概就是维护一个栈,每当找到一个右边界时,弹出所有的左
: 边界进行计算,但是不明白为什么是O(n),因为我觉得有些元素会不止一次的做左边界
: ,leetcode上的一个测试例子是:
: 3,6,5,7,4,8,1,0
: 最大面积是4*5 = 20,但是当8作为右边界开始弹出时,6已经弹出,这样的话如何得到
: 左边界呢?

k****r
发帖数: 807
37
那个能装多少水的那个,我脚的比这个还难呢

【在 p*****2 的大作中提到】
: 不过我觉得这题是我做的所有面试题里差不多最难的。自己根本不可能想出来。
b*****n
发帖数: 482
38
这个真是太简洁了。
今天晚上从有思路到AC,吭哧吭哧花了40分钟,一看二爷给了5分的难度,还挺高兴的
。到这儿一看“菜鸟”的code,才是我的1/3,膜拜。 orz

【在 l*******b 的大作中提到】
: 终于会做了。。。
: int largestRectArea(vector &h) {
: stack p;
: int i = 0, m = 0;
: h.push_back(0);
: while(i < h.size()) {
: if(p.empty() || h[p.top()] <= h[i])
: p.push(i++);
: else {
: int t = p.top();

p*****2
发帖数: 21240
39

装水那个我挺快想出来了。这个没想出来当时。

【在 k****r 的大作中提到】
: 那个能装多少水的那个,我脚的比这个还难呢
b*****n
发帖数: 482
40
装水那个我差了一口气,我左右两个index同时移动了。

【在 p*****2 的大作中提到】
:
: 装水那个我挺快想出来了。这个没想出来当时。

相关主题
请教大家一道Google的题目Google interview question
做了一下Kth small in young tablet 和 largest rectangle contain 1sgoogle 面试题
罗马转数字,数字转罗马问题总结一道题
进入JobHunting版参与讨论
w****x
发帖数: 2483
41

//a binary search solution
int GetBiggestRectBin(int a[], int n)
{
if (n <= 0) return 0;
assert(a);
int nMinIndex = 0;
for (int i = 1; i < n; i++)
if (a[nMinIndex] > a[i])
nMinIndex = i;

int nCur = a[nMinIndex] * n;
int nLft = GetBiggestRectBin(a, nMinIndex);
int nRgt = GetBiggestRectBin(a + nMinIndex + 1, n - 1 -nMinIndex);
return max(nCur, max(nLft, nRgt));
}

【在 l*******b 的大作中提到】
: 终于会做了。。。
: int largestRectArea(vector &h) {
: stack p;
: int i = 0, m = 0;
: h.push_back(0);
: while(i < h.size()) {
: if(p.empty() || h[p.top()] <= h[i])
: p.push(i++);
: else {
: int t = p.top();

p*****2
发帖数: 21240
42

这个我当时想到了。不过复杂度高了些。

【在 w****x 的大作中提到】
:
: //a binary search solution
: int GetBiggestRectBin(int a[], int n)
: {
: if (n <= 0) return 0;
: assert(a);
: int nMinIndex = 0;
: for (int i = 1; i < n; i++)
: if (a[nMinIndex] > a[i])
: nMinIndex = i;

w****x
发帖数: 2483
43

我觉得这题真要问的话给个二分就差不多了,又好写。
基本上写堆栈的感觉肯定是见过了

【在 p*****2 的大作中提到】
:
: 这个我当时想到了。不过复杂度高了些。

p*****2
发帖数: 21240
44
我也这么认为

【在 w****x 的大作中提到】
:
: 我觉得这题真要问的话给个二分就差不多了,又好写。
: 基本上写堆栈的感觉肯定是见过了

c********t
发帖数: 5706
45
这道题我想到的是二分法
存水题也很难想,我试图用两边夹,还是没想出,最后想了一个先找出最大数,然后左
右算分别存水量。

【在 b*****n 的大作中提到】
: 装水那个我差了一口气,我左右两个index同时移动了。
w****x
发帖数: 2483
46

其实这题的O(n)解法和那个移动窗口和直方图蓄水问题很类似,都是保证一个递增或递
减序列然后通过index判断距离。

【在 c********t 的大作中提到】
: 这道题我想到的是二分法
: 存水题也很难想,我试图用两边夹,还是没想出,最后想了一个先找出最大数,然后左
: 右算分别存水量。

c********t
发帖数: 5706
47
嗯,我再复习一下体会体会

【在 w****x 的大作中提到】
:
: 其实这题的O(n)解法和那个移动窗口和直方图蓄水问题很类似,都是保证一个递增或递
: 减序列然后通过index判断距离。

s*****n
发帖数: 994
48
挖个旧坑再问这道题
对于每个i,如果进到else{}中,为什么只要求和上一个top之间的面积?为什么不能
是和top下面的height形成的矩形面积更大?

【在 l*******b 的大作中提到】
: 终于会做了。。。
: int largestRectArea(vector &h) {
: stack p;
: int i = 0, m = 0;
: h.push_back(0);
: while(i < h.size()) {
: if(p.empty() || h[p.top()] <= h[i])
: p.push(i++);
: else {
: int t = p.top();

1 (共1页)
进入JobHunting版参与讨论
相关主题
histogram问题做了一下Kth small in young tablet 和 largest rectangle contain 1s
google的一道题求解罗马转数字,数字转罗马问题
问个largest rectangle in histogram的问题Google interview question
DP算法占用的空间google 面试题
也发个A家电面经总结一道题
想贴一个我收集的算法高频题的博客不知道有没有人看请问一道题--给一个正方形矩阵,每个元素要么黑色要么白色,请找出最大的纯色子矩阵
【非死不可面经】今天FB面试onsite,求blessO(NlogN) largest rectangle in histogram
请教大家一道Google的题目那个常见的histogram max rectangle 问题
相关话题的讨论汇总
话题: int话题: nminindex话题: max话题: stack