algorithm - “直方图中最大的矩形”和“水最多的容器”之间的区别

Question

http://www.leetcode.com/onlinejudge

我看不出这两个问题之间的区别。对我来说，这两个问题是相同的，但它们不是。

有人可以给我一些提示来解释它们为什么不同。

谢谢

Answer 1

“水容器”解决方案将允许水上升到中间位置以上。对于“最大矩形”问题，矩形不能超过中间条。

Answer 2

“水的容器”问题没有像最大的矩形那样清楚地描述，但是我在一次采访中被问到水的问题。

水的容器基本上是在直方图上的条之间询问最大“山谷”的面积。查看最大矩形示例中的直方图，答案将是“1”，因为该图有两个波谷，左侧是 1x1 波谷，右侧是 1x1 波谷。其中的最大值当然是 1。

Answer 3

它们非常相似。我理解不同之处在于“水容器”将是左墙、右墙和底部（x 轴）（中间的一些线可能很短），它在顶部是开放的。而在“最大矩形”中，构成矩形的所有直方图条都必须到达顶部区域。