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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个leetcode上有 Largest Rectangle in Histogram, O(n)
|
c****n 发帖数: 105 | 4 多谢两位,找到详细的解释了
http://www.geeksforgeeks.org/largest-rectangle-under-histogram/
我的思路对了前一半,但是没想到Segment Tree, 所以找最小值的地方没有简化。
【在 d******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : You can then use this to calculate the max value=1 rectangle in a 0/1 matrix : , without DP.
|