Улавливание дождевой воды  — LeetCode #42

Учитывая n неотрицательных целых чисел, представляющих карту высот, где ширина каждой полосы равна 1, вычислите, сколько воды она может собрать после дождя.

Пример 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.

Пример 2:

Input: height = [4,2,0,3,2,5]
Output: 9

Ограничения:

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

Решения:

Питон

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

C#

class Solution {
    public int Trap(int[] height) {
        if (height.Length == 0) {
            return 0;
        }

        int n = height.Length;
        int left = 0, right = n - 1;
        int leftMax = height[left], rightMax = height[right];
        int ans = 0;

        while (left < right) {
            if (leftMax < rightMax) {
                ans += leftMax - height[left];
                left++;
                leftMax = Math.Max(leftMax, height[left]);
            } else {
                ans += rightMax - height[right];
                right--;
                rightMax = Math.Max(rightMax, height[right]);
            }
        }

        return ans;
    }
}

Ява

class Solution {
    public int trap(int[] height) {
        if (height.length == 0) {
            return 0;
        }

        int n = height.length;
        int left = 0, right = n - 1;
        int leftMax = height[left], rightMax = height[right];
        int ans = 0;

        while (left < right) {
            if (leftMax < rightMax) {
                ans += leftMax - height[left];
                left++;
                leftMax = Math.max(leftMax, height[left]);
            } else {
                ans += rightMax - height[right];
                right--;
                rightMax = Math.max(rightMax, height[right]);
            }
        }

        return ans;
    }
}

JavaScript

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    if (height.length === 0) {
        return 0;
    }

    let n = height.length;
    let left = 0, right = n - 1;
    let leftMax = height[left], rightMax = height[right];
    let ans = 0;

    while (left < right) {
        if (leftMax < rightMax) {
            ans += leftMax - height[left];
            left++;
            leftMax = Math.max(leftMax, height[left]);
        } else {
            ans += rightMax - height[right];
            right--;
            rightMax = Math.max(rightMax, height[right]);
        }
    }

    return ans;
};

Типографический текст

function trap(height: number[]): number {
    if (height.length === 0) {
        return 0;
    }

    let n = height.length;
    let left = 0, right = n - 1;
    let leftMax = height[left], rightMax = height[right];
    let ans = 0;

    while (left < right) {
        if (leftMax < rightMax) {
            ans += leftMax - height[left];
            left++;
            leftMax = Math.max(leftMax, height[left]);
        } else {
            ans += rightMax - height[right];
            right--;
            rightMax = Math.max(rightMax, height[right]);
        }
    }

    return ans;
}

PHP

class Solution {

    /**
     * @param Integer[] $height
     * @return Integer
     */
    function trap($height) {
        if (count($height) === 0) {
            return 0;
        }

        $n = count($height);
        $left = 0;
        $right = $n - 1;
        $leftMax = $height[$left];
        $rightMax = $height[$right];
        $ans = 0;

        while ($left < $right) {
            if ($leftMax < $rightMax) {
                $ans += $leftMax - $height[$left];
                $left++;
                $leftMax = max($leftMax, $height[$left]);
            } else {
                $ans += $rightMax - $height[$right];
                $right--;
                $rightMax = max($rightMax, $height[$right]);
            }
        }

        return $ans;
    }

}

Надеюсь, это поможет! Дайте знать, если у вас появятся вопросы. Не забудьте подписаться и похлопать в поддержку моего контента