LeetCode解説　一日一問　11. Container With Most Water

LeetCodeって？
問題
回答

LeetCodeって？

LeetCode - The World's Leading Online Programming Learning Platform

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

LeetCodeとは、アルゴリズムやデータ構造を実践を通して学べる海外のプログラミング学習サイトです。

2022年12月現在2,000問を超える問題が登録されています。

各問題では、特定の入力をしたときに特定の返り値を出力する関数を作成することを求められます。

正誤判定は自動で行われます。

使用できる言語は、C++、C#、JAVA、Python3、Go、JSなど19言語が用意されています。

私はPython3で解いています。

問題

Container With Most Water - LeetCode

Can you solve this real interview question? Container With Most Water - You are given an integer array height of length n. There are n vertical lines drawn such...

タイトル：11. Container With Most Water

難易度：Medium

内容：

長さ n の整数配列 height が与えられる。height に格納された値は高さを表す。height から二つの値(i, j)を抜き出しコンテナを作成する。コンテナの横方向の長さは j – i 、縦方向の長さは min(height[i] , height[j])である。最も面積が大きくなるコンテナを探し、その面積を返す。

例：

height = [1,8,6,2,5,4,8,3,7]
返り値: 49

最も面積の大きなコンテナを構成できるのは、２番目と９番目でその面積は 7*7 で49となります。

回答

総当たりで探すやり方と、2 pointerを使うやり方を考えてみます。

総当たり

全てのコンテナの組み合わせは _nC₂ 通りになります。

# 総当たり
class Solution:
    def maxArea(self, height: list[int]) -> int:
        max_area = 0
        for i in range(len(height)):
            for j in range(len(height) - i - 1):
                tmp = ((j + i + 1) - i) * min(height[j + i + 1], height[i])
                max_area = max(max_area, tmp)
        return max_area

計算量はループが2回あるのでO(N²)です。

結果

時間かかりすぎと怒られてしまいました。

2 pointer

2 pointerを使って最大面積の組み合わせを見つけます。

まず左端と右端を初期値として面積を計算します。

このとき、height[0]はheight[8]より低いです。
height[8]はheight[0]よりも高いほかの値を組み合わせることで、今以上の面積を作れる可能性がありますが、height[0]は最も遠くにあるheight[8]との組み合わせ以上の面積を作ることができません。

なので、左のpointerを一つ右に移動し面積を計算します。

今度は height[1] > height[8] となったので右のpointerを一つ左に移動します。

pointerの移動を繰り返しながら面積を計算していき、最も大きなものを見つけます。

コード

# 2 pointer
class Solution:
    def maxArea(self, height: list[int]) -> int:
        max_area = 0 # 最大面積
        L = 0 # 左側pointer
        R = len(height) - 1 # 右側pointer
        while L < R: # 左側pointerが右側より小さい限り
            tmp_area = (R - L) * min(height[L], height[R])
            max_area = max(max_area, tmp_area)
            if height[L] < height[R]: # 左側の高さが右側より低ければ
                L += 1 # 左側前進
            else:
                R -= 1 # 右側後退
        return max_area

全ての要素を一度通るので、計算量はO(N)です。

コードはgithubにも保管しています。