모든 챌린지
어려움 2명 해결 정답률 33.3%

Trapping Rain Water

Compute how much rain water an elevation map holds.

배우게 될 내용

  • 각 막대 위에 고이는 물 계산하기
  • 왼쪽과 오른쪽 최댓값 사용하기
  • 두 포인터로 O(n)에 풀기

문제

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에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

코더마다 가장 좋은 통과 풀이입니다. 더 빠르고, 메모리를 덜 쓰고, 평가가 좋은 풀이가 위에 옵니다.

# 코더 언어 시간 메모리 AI 평가 풀이
1 ННикита Python 885 ms - 5/5 코드 보기
2 KKosake82 Python 933 ms - 4/5 코드 보기

다른 사람의 풀이 보기

커뮤니티 솔루션

스포일러: 아래에 2개 전체 솔루션 있음 먼저 직접 풀어보세요. 다른 개발자의 코드와 AI 리뷰도 참고할 수 있습니다. 로그인하고 문제를 풀면 토론에 참여할 수 있습니다.