|
|---|
|
|
|
|
|
|
r*******k
发帖数: 1423 | | h*******e
发帖数: 1377 | 2 类似单调队列dp, 但是这里用stack 维护一个单调的栈 数据结构不是deque | r*******k
发帖数: 1423 | 3 算法解释是这样的：
We have discussed a Divide and Conquer based O(nLogn) solution for this
problem. In this post, O(n) time solution is discussed. Like the previous
post, width of all bars is assumed to be 1 for simplicity. For every bar ‘x
’, we calculate the area with ‘x’ as the smallest bar in the rectangle.
If we calculate such area for every bar ‘x’ and find the maximum of all
areas, our task is done. How to calculate area with ‘x’ as smallest bar?
We need to know index of the first smaller (smaller than ‘x’) bar on left
of ‘x’ and index of first smaller bar on right of ‘x’. Let us call these
indexes as ‘left index’ and ‘right index’ respectively.
We traverse all bars from left to right, maintain a stack of bars. Every bar
is pushed to stack once. A bar is popped from stack when a bar of smaller
height is seen. When a bar is popped, we calculate the area with the popped
bar as smallest bar. How do we get left and right indexes of the popped bar
– the current index tells us the ‘right index’ and index of previous item
in stack is the ‘left index’. Following is the complete algorithm.
【在 h*******e 的大作中提到】
: 类似单调队列dp, 但是这里用stack 维护一个单调的栈 数据结构不是deque
| r*******k
发帖数: 1423 | 4 里面明明说要两边找，left index和right index
可是，只扫描一遍，怎么找right index？
算的时候，为啥right index就是自己？
‘x
left
these
【在 r*******k 的大作中提到】
: 算法解释是这样的：
: We have discussed a Divide and Conquer based O(nLogn) solution for this
: problem. In this post, O(n) time solution is discussed. Like the previous
: post, width of all bars is assumed to be 1 for simplicity. For every bar ‘x
: ’, we calculate the area with ‘x’ as the smallest bar in the rectangle.
: If we calculate such area for every bar ‘x’ and find the maximum of all
: areas, our task is done. How to calculate area with ‘x’ as smallest bar?
: We need to know index of the first smaller (smaller than ‘x’) bar on left
: of ‘x’ and index of first smaller bar on right of ‘x’. Let us call these
: indexes as ‘left index’ and ‘right index’ respectively.
| r*******k
发帖数: 1423 | 5 被这题搞伤心了，sigh
【在 r*******k 的大作中提到】
: 里面明明说要两边找，left index和right index
: 可是，只扫描一遍，怎么找right index？
: 算的时候，为啥right index就是自己？
:
: ‘x
: left
: these
| h*******e
发帖数: 1377 | 6 算法是求当前坐标为正方形（还是长方形）右沿儿的所有最大面积可能。
左沿的情况那个stack结构在 index 遍历经过左沿的时候已经记录了。。
我当时也想了好久，后来出去吃饭时候想明白了，但是最后发现结束的时候还有一个特
殊条件没考虑。
‘x
left
these
【在 r*******k 的大作中提到】
: 算法解释是这样的：
: We have discussed a Divide and Conquer based O(nLogn) solution for this
: problem. In this post, O(n) time solution is discussed. Like the previous
: post, width of all bars is assumed to be 1 for simplicity. For every bar ‘x
: ’, we calculate the area with ‘x’ as the smallest bar in the rectangle.
: If we calculate such area for every bar ‘x’ and find the maximum of all
: areas, our task is done. How to calculate area with ‘x’ as smallest bar?
: We need to know index of the first smaller (smaller than ‘x’) bar on left
: of ‘x’ and index of first smaller bar on right of ‘x’. Let us call these
: indexes as ‘left index’ and ‘right index’ respectively.
| a****g
发帖数: 16 | | r*******k
发帖数: 1423 | | a****g
发帖数: 16 | 9 欢迎光临！
【在 r*******k 的大作中提到】
: 你这个blog真好
: 我要rss订阅，hoho
|
|
|
|
|
|
|
|
