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

問題
1. 原文
2. 内容
方針
1. 前提
2. 実装のイメージ
解答
補足・参考・感想

問題

原文

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i^th 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:

Input: height = [1,8,6,2,5,4,8,3,7] Output: 49 Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

1
2
3

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

Input: height = [1,1] Output: 1

1
2

Input: height = [1,1]
Output: 1

Constraints:

n == height.length

2 <= n <= 10⁵

0 <= height[i] <= 10⁴

内容

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

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

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

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

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

方針

前提

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

実装のイメージ

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

解答

解答1：Python, two pointer

class Solution:
    def maxArea(self, height: List[int]) -> int:
        l = 0
        r = len(height)-1
        #widthは左端から右端までの幅
        width = len(height)-1 
        res = 0
        
        #右端から左に向かって処理
        for w in range(width, 0, -1):
            #右側が高い場合
            if height[l] < height[r]:
                #左の高さ×幅と、resの大きい方をresに代入。左側は1つ右にずらす
                res, l = max(res, height[l] * w), l + 1
            #左右の高さが同じ、もしくは左端が高い場合
            else:
                #右側の高さ×幅と、resの大きい方をresに代入。右側は1つ左にずらす
                res, r = max(res, height[r] * w), r - 1
        #resを返す
        return res

class Solution:

def maxArea(self, height: List[int]) -> int:

l = 0

r = len(height)-1

#widthは左端から右端までの幅

width = len(height)-1

res = 0

#右端から左に向かって処理

for w in range(width, 0, -1):

#右側が高い場合

if height[l] < height[r]:

#左の高さ×幅と、resの大きい方をresに代入。左側は1つ右にずらす

res, l = max(res, height[l] * w), l + 1

#左右の高さが同じ、もしくは左端が高い場合

else:

#右側の高さ×幅と、resの大きい方をresに代入。右側は1つ左にずらす

res, r = max(res, height[r] * w), r - 1

#resを返す

return res

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

解答2：Python, two pointer

class Solution:
    def maxArea(self, height: List[int]) -> int:
        #左側のポインタ
        p1 = 0  
        #右側のポインタ
        p2 = len(height) - 1
        #面積
        max_area = 0
        #左右のポインタのインデックスが異なる限り繰り返す
        while p1 != p2:
            #右側の垂直線が低い場合
            if height[p1] > height[p2]:
                #右側の垂直線×左右の幅をareaに代入
                area = height[p2] * (p2 - p1)
                #右側のポインタを一つ左にずらす
                p2 -= 1  
            #左側の垂直線が低い場合
            else:
                #areaに左側の垂直線の高さ×p1～p2までの横幅を代入
                area = height[p1] * (p2 - p1)
                #左側のポインタを一つ右にずらす
                p1 += 1
            #areaがmax_areaよりも大きい場合はmax_areaにareaを代入
            if area > max_area: max_area = area 
        #max_areaを返す
        return max_area

class Solution:

def maxArea(self, height: List[int]) -> int:

#左側のポインタ

p1 = 0

#右側のポインタ

p2 = len(height) - 1

#面積

max_area = 0

#左右のポインタのインデックスが異なる限り繰り返す

while p1 != p2:

#右側の垂直線が低い場合

if height[p1] > height[p2]:

#右側の垂直線×左右の幅をareaに代入

area = height[p2] * (p2 - p1)

#右側のポインタを一つ左にずらす

p2 -= 1

#左側の垂直線が低い場合

else:

#areaに左側の垂直線の高さ×p1～p2までの横幅を代入

area = height[p1] * (p2 - p1)

#左側のポインタを一つ右にずらす

p1 += 1

#areaがmax_areaよりも大きい場合はmax_areaにareaを代入

if area > max_area: max_area = area

#max_areaを返す

return max_area

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

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

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

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

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

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

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

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

解答3：Python , two pointer 2周目

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left = 0
        right = len(height)-1
        max_area = 0
        while left<=right:
            if height[left] < height[right]:
                area = (right-left) * height[left]
                max_area = max(area, max_area)
                left += 1
            else:
                area = (right-left) * height[right]
                max_area = max(area, max_area)
                right -= 1
        return max_area

class Solution:

def maxArea(self, height: List[int]) -> int:

left = 0

right = len(height)-1

max_area = 0

while left<=right:

if height[left] < height[right]:

area = (right-left) * height[left]

max_area = max(area, max_area)

left += 1

else:

area = (right-left) * height[right]

max_area = max(area, max_area)

right -= 1

return max_area

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

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

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

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

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

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

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

解答4：Rust, two pointer

impl Solution {
    pub fn max_area(height: Vec<i32>) -> i32 {
        let (mut res, mut left, mut right) = (0,0, height.len() - 1);
        while left < right {
            let x = (right - left) as i32;
            let mut  y = 0;

            if height[left] < height[right] {
                y = height[left];
                left += 1;
            } else {
                y = height[right];
                right -= 1;
            }

            res = res.max(x * y);
        }
        
        res
    }
}

impl Solution {

pub fn max_area(height: Vec<i32>) -> i32 {

let (mut res, mut left, mut right) = (0,0, height.len() - 1);

while left < right {

let x = (right - left) as i32;

let mut y = 0;

if height[left] < height[right] {

y = height[left];

left += 1;

} else {

y = height[right];

right -= 1;

}

res = res.max(x * y);

}

res

}

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

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

補足・参考・感想

■補足

■参考

前：278. First Bad Version

次：15. 3Sum

LeetCode 解答・解説記事一覧