histogram问题# JobHunting - 待字闺中
J*n
1 楼
http://blog.csdn.net/linulysses/article/details/5594141
这里有对largest rectangle under histogram, maximal subsequence和largest
submatrix几类问题的总结，大家可以看看。但是其中largest rectangle under
histogram的O(n)算法我不太理解其正确性。
比如我有这样一个histogram {2,10, 15, 7, 9, 8, 3}，按照其中的代码
i operation stack max u v
[] 0 0 0
1 push 2 [2] 0 0 0
2 push 10 [10,2] 0 0 0
3 push 15 [15, 10,2] 0 0 0
4 pop 15 [10,2] 15 3 3
pop 10 [2] 20 2 3
* push 7 [7,2] 20 2 3
5 push 9 [9, 7,2] 20 2 3
6 pop 9 [7,2] 20 2 3
* push 8 [8, 7,2] 20 2 3
7 pop 8 [7,2] 20 2 3
pop 7 [2] 21 4 6
* push 3 [3,2] 21 4 6
8 pop 3 [2] 21 4 6
pop 2 [] 21 4 6
* 代码里面漏了这一步
按照上面的代码计算出来最大方形面积是21,但是实际的最大方形面积应该是35才对(对
应的u=2, v=6)
这个O(n)的算法我之前也看过，当时没看懂，这次这个看懂了，但是好像这个是错的
有谁知道正确的算法应该怎么修改？
这里有对largest rectangle under histogram, maximal subsequence和largest
submatrix几类问题的总结，大家可以看看。但是其中largest rectangle under
histogram的O(n)算法我不太理解其正确性。
比如我有这样一个histogram {2,10, 15, 7, 9, 8, 3}，按照其中的代码
i operation stack max u v
[] 0 0 0
1 push 2 [2] 0 0 0
2 push 10 [10,2] 0 0 0
3 push 15 [15, 10,2] 0 0 0
4 pop 15 [10,2] 15 3 3
pop 10 [2] 20 2 3
* push 7 [7,2] 20 2 3
5 push 9 [9, 7,2] 20 2 3
6 pop 9 [7,2] 20 2 3
* push 8 [8, 7,2] 20 2 3
7 pop 8 [7,2] 20 2 3
pop 7 [2] 21 4 6
* push 3 [3,2] 21 4 6
8 pop 3 [2] 21 4 6
pop 2 [] 21 4 6
* 代码里面漏了这一步
按照上面的代码计算出来最大方形面积是21,但是实际的最大方形面积应该是35才对(对
应的u=2, v=6)
这个O(n)的算法我之前也看过，当时没看懂，这次这个看懂了，但是好像这个是错的
有谁知道正确的算法应该怎么修改？
