문제

Categories에 Dynammic programming, Array, Two-pointers, Stack, Montonic Stac이라고 한다 (...)

First Attempt

class Solution {
    public int trap(int[] height) {
        boolean start = false;
        boolean end = false;
        
        int startingHeight = 0;
        int endingHeight = 0;

        int waterAmount = 0;

        ArrayList<Integer> subArray = new ArrayList<>(); // to store wells

        for (int i = 1; i < height.length - 1; i++) {
            // 1. find adjacent local maxima
            if (height[i - 1] < height[i] && height[i + 1] < height[i]) {
                if (!start) {
                    subArray = new ArrayList<>();
                    start = true;
                } else if (start && !end) {
                    end = true;
                }
            }
            if (end) {
                subArray.add(height[i]);
                endingHeight = height[i];

                // 2. After finding both, go through one by one. 
                // first we take the min of the starting and ending height to get the maximum height
                int maximumHeight = Math.min(startingHeight, endingHeight);

                // Subtract each height from maximumHeight to get the amount of water
                for (int j = 1; j < subArray.size() - 1; j++) {
                    waterAmount += maximumHeight - subArray.get(j);
                }

                start = false; 
                end = false;
            } else if (start) {
                // if the second local maximum is not found yet, keep adding to ArrayList 
                subArray.add(height[i]);
                if (subArray.size() == 1) {
                    startingHeight = height[i];
                }
            }
        }

        return waterAmount;
    }
}

여러가지 문제들이 있다:
1. start와 end가 같을 수 있다. end가 Local maximum이니 바로 다음 well 의 Start가 될 수 있다.
2. 등등.

Solution

class Solution {
    public int trap(int[] height) {
        int left = 0; 
        int right = height.length - 1; 
        int leftMax = height[0]; 
        int rightMax = height[right];
        int water = 0; 

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

        return water; 
    }
}

결국 intuition은 비슷했다. 하지만 key point는 local maxima가 adjacent하지 않아도 계산할 수 있다는 것이다.

두개의 local maximum을 구했다고 해보자. 그 사이에 또다른 maximum이 있다고 해도 두개를 비교해 더 낮은 높이로 물의 양을 구하고 더 낮은 높이 쪽의 maximum을 옮긴다고 하면 다음 물의 양도 옳게 계산되고 다음 maximum도 옳은 쪽 (left / right)의 maximum으로 배치된다.