42. Trapping Rain Water

[zeikar]

Problem link

https://leetcode.com/problems/trapping-rain-water/

Problem Summary

지도의 높이가 주어지고 비가 왔을 때 얼마나 찰 수 있는지 출력하는 문제.

Solution

물이 어떨 때 차는지 잘 살펴보면 된다.
물이 차는 높이는 현재 기준으로 왼쪽의 최대, 오른쪽의 최대 중 최솟값만큼 채워진다.

그렇다면 왼쪽의 최대, 오른쪽의 최대를 구하면 되는데 필요할 때마다 구하면 시간 초과가 되므로 미리 구해놓으면 된다.

Source Code

from typing import List


class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        left_max = [height[0]] * n
        right_max = [height[n - 1]] * n

        for i in range(1, n):
            left_max[i] = max(left_max[i - 1], height[i])

        for i in range(n - 2, -1, -1):
            right_max[i] = max(right_max[i + 1], height[i])

        res = 0
        for i in range(n):
            res += max(0, min(left_max[i], right_max[i]) - height[i])

        return res