[LeetCode] Trapping Raing Water - Python

Algorithm Problem with Python — 33day

問題の説明📖

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
各棒の幅は1人立面図のn音を表すのではなく、雨上がりにどれだけ水を閉めることができるかを計算する整数を与える.
制限

n == height.length

0 <= n <= 3 * 10⁴

0 <= height[i] <= 10⁵

I/O例
Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
Example 2:
Input: height = [4,2,0,3,2,5]
Output: 9

問題を理解する🔑

この問題は、2つのポインタとスタックを最大限に移動することで解決できます.
2つのポイントを最大限に移動する方法で行いました
まず、実施例1では、最大高さは3であり、最大高さは総体積(値に関係なく)に影響を及ぼさない.
左右を仕切るバリアにすぎません
2つのポイントを一番上のバーに配置し、そのバーに移動してボリュームを確認します.
左右の柱の最大高さと現在の高さの違いに基づいて、水の高さを基準の最大高さ欄まで加算します.

首都コード▼▼

|表示制限「0<=n<=3*10⁴」の場合、高さが0の場合も存在しますので、先に異常処理を行ってください.

最上位バーに基づく左右側検出変数を作成

左右両側の一番高いストリップを検出する変数を作成します.

2で作成された変数は、最も高いカラムに達するまでポインタをローエンドからハイエンドに移動します.

コード作成

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        
        volume = 0
        left, right = 0, len(height) - 1
        left_max, right_max = height[left], height[right]
        
        while left < right:
            left_max, right_max = max(height[left], left_max), max(height[right], right_max)
                
            if left_max <= right_max:
                volume += left_max - height[left]
                left += 1
            else:
                volume += right_max - height[right]
                right -= 1
        return volume

整理する😄

この問題はかなり難しい.
有効な解法が見つからず、すべての高さと幅を順番に表示した場合は0(n)²)の時間的複雑さを表します.
このプールでは,このような問題に対して,2つのポインタまたはスタックを用いて0(n)プールを行うことができることを見出した.
最大高さバーの基準となる点によって左右の2つの部分に分けたり、最大高さバーと現在の高さバーの違いを見たりすることができます.
複雑な問題ほど、よく考えれば考えるほど解決しやすいので、複雑さを簡単に分ける練習が必要です.
Reference

朴尚吉,『Pythonアルゴリズムインタビュー』,本のみ(2020),p 180-18.3