c****n
发帖数: 105 | 1 Find the largest rectangle area on a bar graph. Example, if you had a graph
of 1,4,5,3,3,5 the answer would be 15 (3x5) which is formed by the rectangle
that is 3 high and spans from position 2 (1 based) to 6.
笨办法自然是N^2，有好办法没？
还有，哪里能找到些system design和distributed system的题目，包括解答呢？ 大部
分DS和Algo的题容易，这两个好像资源不太多啊。 |
s******7
发帖数: 1758 | 2 这个leetcode上有 Largest Rectangle in Histogram， O(n) |
d******g
发帖数: 38 | 3 re，用栈，类似的还有contain water
【在 s******7 的大作中提到】
: 这个leetcode上有 Largest Rectangle in Histogram， O(n)
|
c****n
发帖数: 105 | 4 多谢两位，找到详细的解释了
http://www.geeksforgeeks.org/largest-rectangle-under-histogram/
我的思路对了前一半，但是没想到Segment Tree, 所以找最小值的地方没有简化。
【在 d******g 的大作中提到】
: re，用栈，类似的还有contain water
|
s****g
发帖数: 43 | 5 You can then use this to calculate the max value=1 rectangle in a 0/1 matrix
, without DP. |
d******g
发帖数: 38 | 6 这个需要遍历不同的起始高度，和DP一样都是O(n^2)吧
matrix
【在 s****g 的大作中提到】
: You can then use this to calculate the max value=1 rectangle in a 0/1 matrix
: , without DP.
|
