Trapping Rain Water

Solve 1) Two Pointer

문제 요약

• n개의 막대(height[i]), 막대 폭은 1.
• 전체 물의 양을 구하라.
• 제약: 1 ≤ n ≤ 2 × 10⁴, 0 ≤ height[i] ≤ 10⁵.

직관 ▶ 투 포인터로 압축하기

1️⃣ 물 높이 식

• maxLeft[i] : i 기준 왼쪽에서 본 최고 높이
• maxRight[i] : i 기준 오른쪽에서 본 최고 높이
• 낮은 쪽 벽이 물 높이를 제한한다.

2️⃣ 불변식(Invariant)

아직 처리되지 않은 구간 (L, R)의 끝점에는
반드시 "탐색되지 않은 벽"이 남아 있다.

• 현재 height[L] < height[R]이면 L이 물 높이 제한
• 이때 (1)식을 계산하면 추가 정보가 뒤에서 와도 바뀌지 않는다.

3️⃣ 알고리즘

변수	의미
L, R	왼쪽·오른쪽 포인터
maxL, maxR	현재까지 본 좌·우 최고 높이
water	누적 물 양

int trap(const vector<int>& h){
    int L = 0, R = (int)h.size() - 1;
    int maxL = 0, maxR = 0;
    long long water = 0;
    while(L < R){
        if(h[L] < h[R]){
            maxL = max(maxL, h[L]);
            water += maxL - h[L];
            ++L;
        } else {
            maxR = max(maxR, h[R]);
            water += maxR - h[R];
            --R;
        }
    }
    return (int)water;
}

4️⃣ 복잡도 분석

	시간	메모리
투 포인터	O(n)	O(1)
DP(누적 최대)	O(n)	O(n)	두 배열 저장 필요

시각적 흐름 (ASCII)

높이: 0 1 0 2 1 0 1 3 2 1 2 1
포인터:
L=0 R=11   maxL=0 maxR=1  ← 0 물 0
L=1 R=11   maxL=1 maxR=1  ← 0 물 0
L=2 R=11   maxL=1 maxR=1  ← 1 물 +1
...

(전체 로그는 생략. 직접 찍어보면 불변식이 눈에 보인다!)

왜 "구간별 분할"이 된다 – 귀류법 스케치

1. height[L] < height[R]라 가정.

2. 나중에 오른쪽에서 더 낮은 벽이 등장해 water[L]이 바뀐다면

   • 그 벽은 height[L]보다 더 낮다 ⇒ 물이 더 못 찬다.

3. 모순. 고로 water[L]은 확정값.

동일 논리로 오른쪽 포인터도 증명 완료 ✅

마무리 & 확장 학습

• 동일 패턴 문제

  • LeetCode 11. Container With Most Water
  • BOJ 2473. 세 용액 (Three Pointers 변형)

• 2D 버전

  • LeetCode 407. Trapping Rain Water II – BFS + 우선순위큐

---