동적 프로그래밍 day66_42. 빗물 잡기

폭이 음수가 아닌 정수로 이루어진 각 기둥의 높이 그래프가 주어졌을 때, 이런 식으로 배열된 기둥에 비가 내린 후 얼마나 많은 빗물이 모일지 계산합니다.

예 1:

입력: 높이= [0,1,0,2,1,0,1,3,2,1,2,1]
출력: 6
설명: 위는 배열의 결과입니다.[0,1,0,2,1,0,1,3,2,1,2,1] 높이 지도의 표현, 이 경우 6 단위의 비를 포착합니다. 

예 2:

입력: 높이= [4,2,0,3,2,5]
출력: 9

팁:

• n == height.length
• 1 <= n <= 2 * 401
• 0 <= height[i] <= 501

문제 해결:

아이디어: 더블 포인터

시간 복잡도: O(n)

공간 복잡도: O(1)

class Solution {
 public int trap(int[] height) {
 int n = height.length;
 int res = 0;
 // 왼쪽 및 오른쪽 포인터: 각각 왼쪽 및 오른쪽 경계를 가리키는 열
 int left = 0, right = n - 1;
 // 왼쪽 포인터의 왼쪽 최대 높이, 오른쪽 포인터의 오른쪽 최대 높이
 int leftMax = height[left], rightMax = height[right];
 // 먼 쪽의 기둥은 물을 담지 않습니다.
 left++;
 right--;
 // 중앙에 더 가까이 이동하기
 while(left <= right){
 leftMax = Math.max(leftMax, height[left]);
 rightMax = Math.max(rightMax, height[right]);
 if(leftMax < rightMax){
 // 왼쪽 포인터의 왼쪽 최대값이 오른쪽 포인터의 오른쪽 최대값보다 짧음
 // 설명: 왼쪽 포인터의 오른쪽에 적어도 하나의 보드가 있습니다.> 왼쪽 포인터가 모든 보드를 떠남
 // 버킷 효과에 따르면, 왼쪽 포인터의 현재 열에 있는 물의 양에 대한 결정이 왼쪽에 있다는 것이 보장됩니다.
 // 그런 다음 왼쪽 포인터의 현재 기둥에 있는 물의 양을 계산할 수 있습니다: 왼쪽의 최대 높이 - 현재 기둥의 높이입니다.
 res += leftMax - height[left];
 left++;
 }else{
 // 오른쪽도 동일
 res += rightMax - height[right];
 right--;
 }
 }
 return res;
 }
}