문제
Bars of width 1 have the given heights. After rain, water collects above each bar up to the lower of the tallest bars on its left and right. Compute the total trapped water. An O(n) two-pointer solution is expected.
Implement trapped_water(heights).
Input
heights: Bar heights from left to right.
Output
Return the total units of water.
제약 조건
0 ≤ length ≤ 200,000; 0 ≤ height ≤ 100,000
예시
예시 1
입력:
heights = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
예상 출력:
expected = 6입력:
std::vector<long long> heights = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
예상 출력:
long long expected = 6;입력:
long[] heights = new long[] {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
예상 출력:
long expected = 6;설명
Water fills the dips: 1 + 1 + 2 + 1 + 1 = 6 units.
예시 2
입력:
heights = [3, 2, 1]
예상 출력:
expected = 0입력:
std::vector<long long> heights = {3, 2, 1};
예상 출력:
long long expected = 0;입력:
long[] heights = new long[] {3, 2, 1};
예상 출력:
long expected = 0;설명
Heights only go down, so water runs off: 0.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
각 위치의 물 높이는 왼쪽과 오른쪽에서 본 가장 높은 벽 중 더 낮은 쪽에 의해 제한됩니다.
힌트 2
양쪽 끝에서 경계를 추적하고, 현재 경계가 더 낮은 쪽을 항상 이동하세요.
힌트 3
빈 입력과 같은 높이의 평탄 구간에 주의하세요. 그 구간의 물은 더 낮은 쪽만 결정합니다.
예상 복잡도
시간 O(n), 추가 공간 O(1)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.