algorithm - 「ヒストグラムで最大の長方形」と「水が最も多い容器」の違い

Question

http://www.leetcode.com/onlinejudge

これら 2 つの質問の違いがわかりません。私にとって、これら 2 つの質問は同じですが、そうではありません。

誰かが私にそれらが異なる理由を説明するヒントを教えてもらえますか.

ありがとうございました

Answer 1

「水の容器」ソリューションは、水が中間位置より上に上昇することを可能にします。「最大の長方形」の問題では、長方形は中間バーの上に上がることはできません。

Answer 2

「水の容器」の質問は、最大の長方形のものほど明確に説明されていませんが、インタビューで水の容器について尋ねられました.

水の入った容器は基本的に、ヒストグラムの棒の間にある最大の「谷」の面積を求めています。最大の長方形の例のヒストグラムを見ると、グラフによって作成された 2 つの谷 (左側に 1x1 の谷、右側に 1x1 の谷) があるため、答えは "1" になります。これらの最大値はもちろん 1 です。

Answer 3

それらは非常に似ています。違いは、「水の容器」は左の壁、右の壁、下（x軸）であり（その間のいくつかの線は短い場合があります）、上部が開いていることを理解しています。一方、「最大の長方形」では、長方形を構成するすべてのヒストグラム バーが上部領域に到達する必要があります。