x***y
发帖数: 633 | | r**u
发帖数: 1567 | 2 思路是这样的，
1. 如果所有的bar都是按升序从左到右排起来的话，那么，就可以简单的用最小（最左
）的bar的高*n, n是bar的个数，这是一个面积，接着用次小的bar的高*(n-1), ...,
找到max area。
2. 一般bar不是完全按升序排列。就用一个vector去simulate a stack，如果下一个
bar比栈顶的bar高，入栈。
否则的话，pop栈里所有比next bar高的bar，再入栈next bar。并且要计算这过程
中这些pop掉的bar cover的area。
3. 最后处理剩在stack里面的bar。
【在 x***y 的大作中提到】
: .....
| s*********i
发帖数: 66 | 3 这样计算的面积不重复吗？
【在 r**u 的大作中提到】
: 思路是这样的，
: 1. 如果所有的bar都是按升序从左到右排起来的话，那么，就可以简单的用最小（最左
: ）的bar的高*n, n是bar的个数，这是一个面积，接着用次小的bar的高*(n-1), ...,
: 找到max area。
: 2. 一般bar不是完全按升序排列。就用一个vector去simulate a stack，如果下一个
: bar比栈顶的bar高，入栈。
: 否则的话，pop栈里所有比next bar高的bar，再入栈next bar。并且要计算这过程
: 中这些pop掉的bar cover的area。
: 3. 最后处理剩在stack里面的bar。
| r**m
发帖数: 163 | 4 http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html
里面最后一道题:largest rectangle in histogram
【在 x***y 的大作中提到】
: .....
| s*****i
发帖数: 355 | 5 你这不是O(n)
【在 r**u 的大作中提到】
: 思路是这样的，
: 1. 如果所有的bar都是按升序从左到右排起来的话，那么，就可以简单的用最小（最左
: ）的bar的高*n, n是bar的个数，这是一个面积，接着用次小的bar的高*(n-1), ...,
: 找到max area。
: 2. 一般bar不是完全按升序排列。就用一个vector去simulate a stack，如果下一个
: bar比栈顶的bar高，入栈。
: 否则的话，pop栈里所有比next bar高的bar，再入栈next bar。并且要计算这过程
: 中这些pop掉的bar cover的area。
: 3. 最后处理剩在stack里面的bar。
| g*******y
发帖数: 1930 | 6 是O(n)的
【在 s*****i 的大作中提到】
: 你这不是O(n)
| S******n
发帖数: 1009 | 7 yes, each bar will be pushed and poped at most once
【在 s*****i 的大作中提到】
: 你这不是O(n)
| C***n
发帖数: 452 | 8 one question here, if there are bars Bi, Bi-1, Bi-2 in the stack top that
are higher than current bar Bj
if you remove (Bi, Bi-1, Bi-2), and then push Bj to stack, how do you know
how many bars higher than Bj?
Also, if you meet a bar Bj height equals to the stack top Bi, what will you
do?
Anybody please share if you get clear ideas about this, thanks.
【在 r**u 的大作中提到】
: 思路是这样的，
: 1. 如果所有的bar都是按升序从左到右排起来的话，那么，就可以简单的用最小（最左
: ）的bar的高*n, n是bar的个数，这是一个面积，接着用次小的bar的高*(n-1), ...,
: 找到max area。
: 2. 一般bar不是完全按升序排列。就用一个vector去simulate a stack，如果下一个
: bar比栈顶的bar高，入栈。
: 否则的话，pop栈里所有比next bar高的bar，再入栈next bar。并且要计算这过程
: 中这些pop掉的bar cover的area。
: 3. 最后处理剩在stack里面的bar。
| l*******r
发帖数: 511 | 9 equal就skip呗
这个题的关键是理解最大的矩形肯定要以某个unit为高。。而这个unit能extend到多左
边多
右边则是由stack里的比它低的那个和将要让它pop的那个决定的
one question here, if there are bars Bi, Bi-1, Bi-2 in the stack top that
are higher than current bar Bj
if you remove (Bi, Bi-1, Bi-2), and then push Bj to stack, how do you know
how many bars higher than Bj?
Also, if you meet a bar Bj height equals to the stack top Bi, what will you
do?
Anybody please share if you get clear ideas about this, thanks.
【在 C***n 的大作中提到】
: one question here, if there are bars Bi, Bi-1, Bi-2 in the stack top that
: are higher than current bar Bj
: if you remove (Bi, Bi-1, Bi-2), and then push Bj to stack, how do you know
: how many bars higher than Bj?
: Also, if you meet a bar Bj height equals to the stack top Bi, what will you
: do?
: Anybody please share if you get clear ideas about this, thanks.
| C***n
发帖数: 452 | 10 if you skip this equal ones, how do you count it in the max area later?
full solution, please, especially how the max area is updated in each case
you
【在 l*******r 的大作中提到】
: equal就skip呗
: 这个题的关键是理解最大的矩形肯定要以某个unit为高。。而这个unit能extend到多左
: 边多
: 右边则是由stack里的比它低的那个和将要让它pop的那个决定的
:
: one question here, if there are bars Bi, Bi-1, Bi-2 in the stack top that
: are higher than current bar Bj
: if you remove (Bi, Bi-1, Bi-2), and then push Bj to stack, how do you know
: how many bars higher than Bj?
: Also, if you meet a bar Bj height equals to the stack top Bi, what will you
| | | C***n
发帖数: 452 | 11 apart from bar height, it looks like the stack will also need to record the
starting index of a bar height?
for example, the 6 bar heights go like this:
2 2 3 3 1 5
the stack will be [2 3] after meeting 2 2 3 3, and how to upadte max area
after meeting the height 1 (5th bar)?
finally the stack will be [1 5], how to update max area with this final
stack? thanks.
you
【在 l*******r 的大作中提到】
: equal就skip呗
: 这个题的关键是理解最大的矩形肯定要以某个unit为高。。而这个unit能extend到多左
: 边多
: 右边则是由stack里的比它低的那个和将要让它pop的那个决定的
:
: one question here, if there are bars Bi, Bi-1, Bi-2 in the stack top that
: are higher than current bar Bj
: if you remove (Bi, Bi-1, Bi-2), and then push Bj to stack, how do you know
: how many bars higher than Bj?
: Also, if you meet a bar Bj height equals to the stack top Bi, what will you
| g*******y
发帖数: 1930 | 12 stack stores index
the
【在 C***n 的大作中提到】
: apart from bar height, it looks like the stack will also need to record the
: starting index of a bar height?
: for example, the 6 bar heights go like this:
: 2 2 3 3 1 5
: the stack will be [2 3] after meeting 2 2 3 3, and how to upadte max area
: after meeting the height 1 (5th bar)?
: finally the stack will be [1 5], how to update max area with this final
: stack? thanks.
:
: you
| C***n
发帖数: 452 | 13 stack stores both height and index information, like a struct {int height,
int index}? thanks for clarification.
in the previous case, if you pop 2,3 and then push 1, it should be {height:1
, index:0} something like this, is my understanding right?
【在 g*******y 的大作中提到】
: stack stores index
:
: the
| r**u
发帖数: 1567 | 14
对的。你好好琢磨一下，试着code出来，考虑corner cases，没那么难。自己code印象
才深。
【在 C***n 的大作中提到】
: stack stores both height and index information, like a struct {int height,
: int index}? thanks for clarification.
: in the previous case, if you pop 2,3 and then push 1, it should be {height:1
: , index:0} something like this, is my understanding right?
| h*******x
发帖数: 12808 | 15 赞，谢谢了，很好解法。
【在 r**u 的大作中提到】
: 思路是这样的，
: 1. 如果所有的bar都是按升序从左到右排起来的话，那么，就可以简单的用最小（最左
: ）的bar的高*n, n是bar的个数，这是一个面积，接着用次小的bar的高*(n-1), ...,
: 找到max area。
: 2. 一般bar不是完全按升序排列。就用一个vector去simulate a stack，如果下一个
: bar比栈顶的bar高，入栈。
: 否则的话，pop栈里所有比next bar高的bar，再入栈next bar。并且要计算这过程
: 中这些pop掉的bar cover的area。
: 3. 最后处理剩在stack里面的bar。
|
|
