leetcode日記6

KOCはロングコートダディを応援してました。ko_ya346です。

leetcodeだぜヘイヘイ

Container With Most Water

leetcode.com

nが最大10⁵なので、左端と右端を全探索する方法では時間オーバーになります。
尺取り法みたく左側からl, rを少しずつ増やす方法で考えてましたが思いつかず、、、

自力で解けなかったのでhintとdiscussionを全力で参考にしました。

• 両端から徐々に狭めていく
• 左端、右端を使い、溜まった水の面積の最大を更新していく
• 左端、右端のうち、高さの小さい側を移動していく

class Solution:
    def maxArea(self, height: List[int]) -> int:
        l = 0
        r = len(height) - 1
        ans = 0
        
        while l < r:            
            ans = max(ans, min(height[l], height[r]) * (r - l))
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return ans