리트코드 42. Trapping Rain Water

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

Trapping Rain Water - LeetCode

SSAFY 셔틀버스를 타는 1시간동안 멍 때리고 유튜브를 볼 게 아니라 이렇게 알고리즘을 풀 수 있다는 생각을 왜 이제서야 했는지 모르겠다.

무접점 키보드가 아니라 키압이 좀 무거운 바저적을 사용하는게 단점이었는데, 정말 소리가 하나도 안 난다는 장점이 있어서 버스 내에서 알고맂므을 풀 수 있다는 걸 이제야 생각했다

힌트 1. 물은 나보다 큰 벽이 다가왔을 앞에 나왔을 때만 담겨질 수 있다.

힌트 2. 가장 왼쪽 값은 자신보다 같거나 큰 값이 나오기 전까지 바뀌지 않는다.

힌트 3. 자신보다 큰 벽이 왔을 때 물이 담기는 양은 가장 왼쪽 벽과 앞에 나온 벽 중 작은 값 - 각 인덱스의 높이다.

class Solution {
    public int trap(int[] height) {
        int start = 0;
        int[] water = new int[height.length];
        for(int i=1; i<height.length; i++){
            // 이전 값보다 증가했을 경우 물이 찰 가능성이 있음
            if(i!=1 && height[i] - height[i-1] > 0){
                int num = Math.min(height[start], height[i]);
                for(int j=start; j<i; j++){
                    water[j] = Math.max(water[j], num - height[j]);
                }
            }

            if(height[i] >= height[start]){
                start = i;
            }
        }
        int ans = 0;
        for(int num : water){
            ans += num;
        }
        return ans;
    }
}