r*k
2 楼
https://oj.leetcode.com/problems/largest-rectangle-in-histogram/
我写了个递归的，类似二分查找的，
在测试case {0,1,2,...8893}时，直接stackOverFlow了
看了神解答，
https://oj.leetcode.com/discuss/oj/largest-rectangle-in-histogram
但是没看懂
主要是：为啥当前的index就是right_index?
我写了个递归的，类似二分查找的，
在测试case {0,1,2,...8893}时，直接stackOverFlow了
看了神解答，
https://oj.leetcode.com/discuss/oj/largest-rectangle-in-histogram
但是没看懂
主要是：为啥当前的index就是right_index?
g*t
3 楼
gutter什么都是clean 和work的，但是下雨有水从gutter和房檐边之间滴下来 是不是
gutter没装好？
gutter没装好？
t*e
4 楼
买啥呀
h*e
5 楼
类似单调队列dp, 但是这里用stack 维护一个单调的栈 数据结构不是deque
w*4
6 楼
排水管有可能堵住了。天晴的时候，弄一盆水从排水管的入口处倒进去，看看水是不是
能很快从排水管下面的出口出来。如果不能，就需要通一下排水管。可能需要一截一截
拆开。不过并不难，就是拧几个螺丝。一般排水管的拐弯处比较容易堵。
能很快从排水管下面的出口出来。如果不能，就需要通一下排水管。可能需要一截一截
拆开。不过并不难，就是拧几个螺丝。一般排水管的拐弯处比较容易堵。
a*e
7 楼
小心拿不到
【在 m*r 的大作中提到】
: almost everything is deal hehe.
【在 m*r 的大作中提到】
: almost everything is deal hehe.
r*k
8 楼
算法解释是这样的：
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
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
c*2
9 楼
不正常。如上所介绍的或者用其他办法处理。
【在 g********t 的大作中提到】
: gutter什么都是clean 和work的，但是下雨有水从gutter和房檐边之间滴下来 是不是
: gutter没装好？
【在 g********t 的大作中提到】
: gutter什么都是clean 和work的，但是下雨有水从gutter和房檐边之间滴下来 是不是
: gutter没装好？
s*y
10 楼
亏大了，前两天刚买了相机，555555
r*k
11 楼
里面明明说要两边找，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.
可是，只扫描一遍，怎么找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.
m*r
12 楼
以前的还可以，我只是买了wii fit啥的，系统不敢买
【在 a***e 的大作中提到】
: 小心拿不到
【在 a***e 的大作中提到】
: 小心拿不到
r*k
13 楼
被这题搞伤心了，sigh
【在 r*******k 的大作中提到】
: 里面明明说要两边找，left index和right index
: 可是，只扫描一遍，怎么找right index？
: 算的时候，为啥right index就是自己？
:
: ‘x
: left
: these
【在 r*******k 的大作中提到】
: 里面明明说要两边找，left index和right index
: 可是，只扫描一遍，怎么找right index？
: 算的时候，为啥right index就是自己？
:
: ‘x
: left
: these
l*n
14 楼
为啥？
【在 a***e 的大作中提到】
: 小心拿不到
【在 a***e 的大作中提到】
: 小心拿不到
h*e
15 楼
算法是求当前坐标为正方形（还是长方形）右沿儿的所有最大面积可能。
左沿的情况那个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.
左沿的情况那个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.
m*n
16 楼
我昨天beauty.com的都没给, 怕了
【在 m*r 的大作中提到】
: almost everything is deal hehe.
【在 m*r 的大作中提到】
: almost everything is deal hehe.
a*g
17 楼
我这里有个解释，仅供参考：
http://decomplexify.blogspot.com/2014/03/algorithm-max-rectangl
【在 r*******k 的大作中提到】
: 被这题搞伤心了，sigh
http://decomplexify.blogspot.com/2014/03/algorithm-max-rectangl
【在 r*******k 的大作中提到】
: 被这题搞伤心了，sigh
c*a
18 楼
说不定被钓鱼了
r*k
19 楼
你这个blog真好
我要rss订阅，hoho
【在 a****g 的大作中提到】
: 我这里有个解释，仅供参考：
: http://decomplexify.blogspot.com/2014/03/algorithm-max-rectangl
我要rss订阅，hoho
【在 a****g 的大作中提到】
: 我这里有个解释，仅供参考：
: http://decomplexify.blogspot.com/2014/03/algorithm-max-rectangl
c*a
20 楼
说不定被钓鱼了
a*g
21 楼
欢迎光临！
【在 r*******k 的大作中提到】
: 你这个blog真好
: 我要rss订阅，hoho
【在 r*******k 的大作中提到】
: 你这个blog真好
: 我要rss订阅，hoho
c*a
22 楼
说不定被钓鱼了
m*r
23 楼
为什么要钓3次鱼？
【在 c*****a 的大作中提到】
: 说不定被钓鱼了
【在 c*****a 的大作中提到】
: 说不定被钓鱼了
h*a
24 楼
可以多挣点wb
【在 m*r 的大作中提到】
: 为什么要钓3次鱼？
【在 m*r 的大作中提到】
: 为什么要钓3次鱼？
w*a
25 楼
酱紫啊，那俺上机器人钓个两万条鱼，是不是就富了？
【在 h********a 的大作中提到】
: 可以多挣点wb
【在 h********a 的大作中提到】
: 可以多挣点wb
c*e
26 楼
下了个nex-5
【在 c*****a 的大作中提到】
: 说不定被钓鱼了
【在 c*****a 的大作中提到】
: 说不定被钓鱼了
S*g
27 楼
dell的bing cashback一般要多久会显示出来？
【在 c*******e 的大作中提到】
: 下了个nex-5
【在 c*******e 的大作中提到】
: 下了个nex-5
c*y
28 楼
dell得好像都不是instant
【在 S*********g 的大作中提到】
: dell的bing cashback一般要多久会显示出来？
【在 S*********g 的大作中提到】
: dell的bing cashback一般要多久会显示出来？
t*3
29 楼
没有哇，key word？
c*e
30 楼
这个我还真不知道,呵呵,我保存了25%跳转的那个画面
【在 S*********g 的大作中提到】
: dell的bing cashback一般要多久会显示出来？
【在 S*********g 的大作中提到】
: dell的bing cashback一般要多久会显示出来？
相关阅读
该买多大电视呢春晚开始了Share something with you about Mortgage怎么把微波炉装在墙上的 cabinet 的下方？什么是Leaking Underground Storage TanksDown pay must be at least 20%?SELLER的责任不能CLOSE能索赔多少钱？哪位推荐San Jose的越南餐馆新年快乐！又来请教了，关于SHORT SALE...有没有什么快速除掉ice dam的办法？花园 | 我的树咋啦 (转载)求推荐loan broker (转载)show后院桃花refinance 今天终于close了室外电线杆（电灯柱）的base有人做过吗求助 sellers现在拒绝final walk throughoffer rejected求LA除白蚁公司推荐今天忙活了一天REO的房子怎么买？