[leet 42]2つのポインタ、1つずつ移動

2062 ワード
python pointer コーディングテスト テキストリンク
leetcode 42. Trapping Rain Water

上の問題のように,中間容器の幅を求めるという問題では,両端に2つのポインタを置き,内側に縮小し,幅を求める.まずこの方法を覚えてから、まず考えたほうが便利です.
今回の42番目の問題も同じですが、2つのポインタが同時に1つの格を移動している間に、しばらくうろうろしていました.2つのポインタが出会うと,双方が行うmax heightが異なるため,処理すべき例外事項は1,2つではない.一つ一つ移動する方法に変えて、本当に簡単に解けました.

Question



Solution


PSEUDO

  • 両端ダブルポインタの使用

  • 左<右、左/右、右/右、左/右それぞれ1マスずつ移動

  • height[左+1]left_temp += left_max-height[left+1]

  • Else:(より大きいか等しい場合はtemp決済)
    ans += left_temp
    left_temp = 0
    left_max = height[left+1]
    left += 1

  • (右側で同様の操作を行います)

  • 最後に移動しながら会うとans+left temp+right tempを加えて戻ります
    • tempはいらないかもしれませんが、ansに直接付けても大丈夫です.
    2つの位置が同時に1つのグリッドを移動すると、2つの最大値が異なるため、中間で複雑になります.(問題を解くのが難しい)一人一人!
    from typing import List

def trap(height: List[int]) -> int:
    if len(height) <= 2: return 0

    left_idx = 0
    right_idx = len(height)-1
    ans = 0
    left_temp, right_temp = 0, 0
    left_max, right_max = height[0], height[-1]

    while left_idx < right_idx:
        if left_max <= right_max:
            if height[left_idx+1] < left_max:
                left_temp += (left_max - height[left_idx+1])
            else:
                ans += left_temp
                left_temp = 0
                left_max = height[left_idx+1]
            left_idx += 1
        else:
            if height[right_idx-1] < right_max:
                right_temp += (right_max - height[right_idx-1])
            else:
                ans += right_temp
                right_temp = 0
                right_max = height[right_idx-1]
            right_idx -= 1
    return ans + left_temp + right_temp
    github
    🦎 [深潜学習]3 rd-40イベントハンドラ
    完走していない選手