x*****o
发帖数: 23 | 1 “给你 n 个数字 a1,a2...an,表示坐标上面(i,ai)个点,i=1..n(i,ai)到(i,0)共 n 个
线段,从中挑两条,和 x 轴一起构成一个容器,让容器能装的液体容量最大(容器不能倾
斜)。”
应该是可以O(N)吧？ | r*******g
发帖数: 1335 | 2 这个是求直方图最大面积的变种，有O(N)的办法。 | f*******t
发帖数: 7549 | 3 能解释下思路吗？
【在 r*******g 的大作中提到】
: 这个是求直方图最大面积的变种，有O(N)的办法。
| r*******g
发帖数: 1335 | 4 我仔细想了下，对题意有点不理解了,到底上面的线段是不是就是盖子？如果没有盖子
，那液体可以到处流动，这个题就很奇怪了。
假设选的是如下的线段
(1,3),(2,2),(3,3)，那么容积是5，是不是？
再比如
(1,3),(2,2),(3,0.5)，左边部分的水会往下流吗
我倾向于上面的线段就是盖子,这样的话，每相邻两条线段的面积，就可以等效于一个
直方图，然后，回到那个经典题目。
【在 f*******t 的大作中提到】
: 能解释下思路吗？
| H****s
发帖数: 247 | 5 这题跟直方图那题不一样吧！我理解的题目是只考虑左右两边的线段和x轴构成的水桶
，跟中间的线段没关系。(1,3),(2,2),(3,3)等效于 （1，3）， （3，3）所以容积是6 | f*******t
发帖数: 7549 | 6 我的理解是直方图只取其中两条竖线，与X轴构成一个容器。
假设直方图高度存在一个数组A中，比如[1, 3, 2, 4, 1]，那么最大容积是
max( min(A[i], A[j]) * (j-i) ) for all i
穷举显然是O(n^2)，感觉可能有线性解法但实在想不出来。 | H****s
发帖数: 247 | |
|
