.png&blockId=5f7573ad-6867-4d59-999e-722aced04aeb)
Hard
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Example 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
Plain Text
복사
Example 2:
Input: height = [4,2,0,3,2,5]
Output: 9
Plain Text
복사
Constraints:
•
n == height.length
•
1 <= n <= 2 * 104
•
0 <= height[i] <= 105
My solution
2차원 배열으로 1과 0으로 채워진 배열을 만든다. indexOf와 lastIndexOf를 사용해서 행에서 처음 만나는 1과 마지막 만나는 1의 인덱스가 다르다면 빗물을 채울 수 있다고 예상했다. 이때 이 두 인덱스를 slice()의 범위에 넣어서 배열을 자른다음 filter로 잘라서 길이를 구했다. 그런데 이렇게 하면 처음으로 시간 초과가 났다.
투포인터를 적용하든 해서 이중 for문이 없어야 하고 시간복잡도가 O(n^2)되서는 안된다.
10^4만큼의 인풋이 들어오는데 제곱을 하면 시간초과가 된다.
Code
const trap = function (height) {
// 투포인터의 lt = 0, rt = length-1; 기본값
let left = 0;
let right = height.length - 1;
// 누적시킬 물의 양
let maxWater = 0;
// 왼쪽 기준 높이값(들어온 요소의 높이랑 빼주기 위해서 필요)
let leftMax = height[left];
// 오른쪽 기준 높이값(들어온 요소의 높이랑 빼주기 위해서 필요)
let rightMax = height[right];
// 왼쪽에서 오른쪽, 범위 조절하면서 탐색
while (left < right) {
// 배열에서 왼쪽 높이보다 오른쪽 높이가 크면?
// -> mid는 바로 해도 lt, rt는 어떤 조건에 따라 업데이트됨.
// 그리고 그 업데이트된 인덱스로 값에 접근해서 max에서 빼 누적함
// -> 다음 값은 지금 높이가 더 크다면 그걸 기준으로 해야 되므로 업데이트함
if (height[left] < height[right]) {
left++;
maxWater += Math.max(0, leftMax - height[left]);
leftMax = Math.max(leftMax, height[left]);
} else {
right--;
maxWater += Math.max(0, rightMax - height[right]);
rightMax = Math.max(rightMax, height[right]);
}
}
return maxWater;
};
JavaScript
복사
