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一般要多久会显示出来？
相关阅读
请问贷款可以只看一年收入吗？请教：怎么上SCOT的杀蒲公英的化肥？急！求教：乱涨价和收早取消费的问题如何更换坏灯泡在high ceiling开败了的郁金香要怎么打理？哪里查租客的credit report最方便？ (转载)最近上买卖提browser常被冻住求助，帮忙看看landscape/lawn care这个价格靠铺不房屋贷款，求好的loanAPI's are permanently removed after 2 yrs in CA后院积水可行方法。后院有两个drainage cover，builder把后院建成小山一样，不肯加土减小坡度投资房，如果花了很多钱去装修，是不是也要做到税收的成本里面去呀？家门口的门铃不响，怎么办。找房贷私人贷款公司说能match就没啥意思了吧？当当当．．．．三月水枪请教：关于double patio door想在二楼铺实木地板，想想问问大家地板下面铺哪一种underlayment合适?为啥我就是不喜欢LOW'S 而喜欢家得宝呢？餐桌上的吊灯不亮了