NeetCodeのSolutionを書いていく

#

Container With Most Water

#

問題概要

#

i番目の棒を意味するheightsという整数の配列が与えられます。 ２つの任意の棒を選択して容器を作りましょう。 コンテナが保持できる最大の量を返しましょう。

制約

• 高さは2以上、1000以下
• 配列サイズは0以上1000以下

計算：O(n) メモリ：O(1)

例

#

Input: height = [1,7,2,5,4,7,3,6] Output: 36

Input: height = [2,2,2] Output: 4

メモ

#

量、の定義は配列の添字を横の区間に、配列の値を縦方向に捉えた時の面積のような感じ。 なので例1の場合は7と6で挟まれた6区間 x 高さ6 = 36 例2の場合は 2と2で挟まれた2区間 x 高さ2 = 4

Tow Pointer なので、データの前後から調査をするはず。 O(n)なのでループは一つ。 ループ2つでやれば簡単なので、ループ1つでどうやるかを問う問題。

   | |
___|_|___

_|_____|_

上記２つだと上は2下は5で下の方がコンテナ容量は大きい。

    | |
_|__|_|__|_

という形で水が貯まると6になりそうな気もするが、とりあえずそれは考えなくて良さそう。 左右から棒の高さを調べていく。 棒の高さが低い方を次に進めて容量を計算する。 容量が小さくなったらその時点で最大値を返す。 ループ2つだけど、左右から近寄っていくので高々n回しか処理しない感じ。

from typing import List


class Solution:
    def maxArea(self, heights: List[int]) -> int:
        left = 0
        right = -1
        length = len(heights)
        max = 0
        while True:
            if (left + abs(right)) > length:
                return max
            cap = min(heights[left], heights[right]) * (length + right - left)
            if max < cap:
                max = cap

            if heights[left] > heights[right]:
                right = right - 1
            else:
                left = left + 1