【LeetCode】11. Container With Most Water 解いてみた【Medium】

問題の概要

2つの棒で作れる最大の長方形の面積を求める
幅はインデックスの

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

最初に考えた解き方

・左右にポインターを配置
・値が小さい方を高さとして面積を計算。それをスタックと比較して大きいなら格納
・値が小さい方のポインターを内側へ。（それ以上大きい幅になることはないので）
・l>=rになったら終了

両方同じなら？？
＞どっちでもいのでは

わかりそうでわからない

何がよくなかったか？

面積を幅＊高さで考えようとしていたが、各インデックスごとに幅は考慮せずに高さだけ足していけば解決できたと思う

解き方

左右のマックスの低い方より低い分だけ水を入れれる

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0

        l, r = 0, len(height) - 1
        leftMax, rightMax = height[l], height[r]
        res = 0
        while l < r:
            if leftMax < rightMax:
                l += 1
                leftMax = max(leftMax, height[l])
                res += leftMax - height[l]
            else:
                r -= 1
                rightMax = max(rightMax, height[r])
                res += rightMax - height[r]
        return res

簡単に見えてしまうのが怖い

考え方がスマートすぎる
頭が上がらない

参考資料

おわりに

すぐ近くに答えはあったりする。
今の考えを少し捻ったらどうなる？？