leetcode: Trapping Rain Water

브루트포스 방법으로 양 옆을 다 보는 방법의 경우 시간복잡도 O(N^2)이 걸릴 것이다.

 

이 문제의 경우 아래와 같이 왼쪽에  있는 높이 중에서 가장 높은 높이만 보고 있는 상태이므로

=> 스택을 사용한다면 O(N)만에 문제를 풀 수 있다.

https://leetcode.com/problems/trapping-rain-water/

문제풀이 로직은 아래와 같다.

1. index를 오른쪽으로 움직이면서 스택의 맨 위에 담은 높이와 비교했을때 height[index]이 크거나 같으면 스택에 담는다.

2. 높이가 바뀌면 이전까지 물을 계산해서 answer에 더해주며, 이전 높이는 pop 시켜준다.

import java.util.*;
class Solution {
	public int trap(int[] height) {
		int answer = 0;

		Stack<Integer> stack = new Stack<Integer>();
		int index = 0;
		while (index < height.length) {
			while (!stack.isEmpty() && height[index] >= height[stack.peek()]) {
				int top = stack.pop();

				if (stack.isEmpty()) {
					break;
				}
				int distance = index - stack.peek() - 1;
				int bounded_height = Math.min(height[index], height[stack.peek()]) - height[top];
				answer += distance * bounded_height;
			}
			stack.push(index++);
		}

		return answer;
	}
}