[#0042 빗물 담기] O(1) 공간 투 포인터 풀이 정리

문제 #0042 빗물 담기를 O(1) 공간으로 푸는 표준 풀이 정리합니다.

핵심 아이디어: 두 포인터 l, r을 양 끝에서 좁혀오면서, 더 낮은 쪽의 lmax/rmax를 기준으로 물을 쌓는다.

왜 이게 되는가? — 더 낮은 벽 쪽은 반대편에 무조건 더 높은 벽이 존재한다는 게 보장됨. 따라서 그 사이에서는 lmax 또는 rmax 중 더 낮은 쪽이 곧 물 높이의 상한.

시간 O(n), 공간 O(1). 본문에 코드 첨부.

function trap(h) {
  let l = 0, r = h.length - 1;
  let lmax = 0, rmax = 0, water = 0;
  while (l < r) {
    if (h[l] < h[r]) {
      h[l] >= lmax ? lmax = h[l] : water += lmax - h[l];
      l++;
    } else {
      h[r] >= rmax ? rmax = h[r] : water += rmax - h[r];
      r--;
    }
  }
  return water;
}