Trapping Rain Water[자주 나오는 물 채우기 DP문제][Array,Two Pointers,Dynamic Programming,Stack,Monotonic Stack]

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

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.

 

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

 

Constraints:

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

 

향간에 자주 떠도는 물채우기 문제이다.

구찮은 녀석..

 

뭔가 방법론을 알 거 같으면서도 여전히 이해가 어렵다.

이해는 못 했지만 방법만 암기한 느낌

뭐이리 어렵

// Time:  O(n)
// Space: O(1)

class Solution {
public:
    int trap(vector<int>& height) {
        int result = 0, left = 0, right = height.size() - 1, level = 0;
        while (left < right) {
            int lower = height[height[left] < height[right] ? left++ : right--];
            level = max(level, lower);
            result += level - lower;
        }
        return result;
    }
};

// Time:  O(n)
// Space: O(1)
class Solution2 {
public:
    int trap(vector<int>& height) {
        if (height.empty()) {
            return 0;
        }

        int i = 0, j = height.size() - 1;
        int left_height = height[0];
        int right_height = height[height.size() - 1];
        int trap = 0;

        while (i < j) {
            if (left_height < right_height) {
                ++i;
                // Fill in the gap.
                trap += max(0, left_height - height[i]);
                // Update current max height from left.
                left_height = max(left_height, height[i]);
            }
            else {
                --j;
                // Fill in the gap.
                trap += max(0, right_height - height[j]);
                // Update current max height from right.
                right_height = max(right_height, height[j]);
            }
        }

        return trap;
    }
};

 

DP로 푸는 법은 아래와 같다.

 

쉽지가 않어

def trap(height):
    if not height:
        return 0

    n = len(height)
    left_max = [0] * n
    right_max = [0] * n

    # 왼쪽 최대 높이 계산
    left_max[0] = height[0]
    for i in range(1, n):
        left_max[i] = max(left_max[i - 1], height[i])

    # 오른쪽 최대 높이 계산
    right_max[n - 1] = height[n - 1]
    for i in range(n - 2, -1, -1):
        right_max[i] = max(right_max[i + 1], height[i])

    # 물의 양 계산
    water_trapped = 0
    for i in range(n):
        water_trapped += min(left_max[i], right_max[i]) - height[i]

    return water_trapped

 

코드를 따라가면 솔직히 와닿진 않는데,

 

기가 막히게 여러 case에서 잘 동작한다.

 

아~~ 근데 와닿지가 않아서 찝찝하무니다!!! 아오