スポンサーリンク

【LeetCode】11. Container With Most Water 解答・解説【Python】

スポンサーリンク
スポンサーリンク
この記事は約4分で読めます。

 

問題

原文

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

 

Example 1:

Example 2:

 

Constraints:

  • n == height.length
  • 2 <= n <= 105
  • 0 <= height[i] <= 104

 

内容

長さnの高さを集めた配列が与えられます。

i番目の直線の2つの端点が(i,0)、(i,height)であるようにn本の垂直線が描かれています。

最も多くの水を含む箱を形作るような、x軸に合った2本の直線を求めてください。

なお、箱は斜めにすることはできません。

 

※正しくない可能性があります。

方針

前提

  1. 左右の端点を示す2つのポインタを使う

実装のイメージ

  • 両端からスタートして低い方の高さを使って面積を求める。
  • 最大面積を更新しながら、1つずつ両端の幅を狭める

解答

解答1:Python, two pointer

右端から逆順で処理する理由はちょっとわからない。

 

解答2:Python, two pointer

解答1よりもこちらの方がわかりやすい。

p1は左側の縦線、p2は右側の縦線を示すポインタ。

ポインタと書いているが、メモリ上のアドレスを示すものではなくリスト内のどの要素を指しているかと言う意味で便宜的にポインタと書いているものだと思う。

左右のポインタは両端から内側に一つずつずらしていく。

ポインタが重なったら終了。

それまでは、面積を求めて、最大面積と比較して更新する。

縦線の高さが低い方を指しているポインタを一つ内側にずらすことを繰り返していく。

ループが終わったら値を返す。

解答3:Python , two pointer 2周目

2回目に解いたときの解答。

解答2と一番異なる点はwhileの条件。

leftポインタがrightポインタと位置関係が入れ替わるまで繰り返しを行った。

この解答を書いている時、if文とelse文の中で、それぞれleft,rightポインタのどちらを動かせば良いかで迷った。

高さが小さい方のポインタを内側に動かす操作で良かった。

2つの縦線で作られる四角形の最大面積を求めるので、常に高い方の縦線はできるだけ動かさないようにしておく必要があるからだと思う。

高い方のポインタを先に内側に動かしてしまうと、反対側のポインタを動かしたときに、まだ最大面積となる組み合わせをスルーしてしまう可能性がある。

解答4:Rust, two pointer

写経。解答3に近いと思う。

Rustでは、複数の変数を1行でまとめて書きたいときは、()で囲む必要がある?

 

 

補足・参考・感想

■補足

■参考

 

 

前:278. First Bad Version

次:15. 3Sum

LeetCode 解答・解説記事一覧

コメント