LC42. Trapping Rain Water

작성일

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

  • 이제는 너무 많이 풀어서 익숙한 수족관 문제
  • stack으로도, left-right array 두개 만들어서도 풀수 도 있고
  • 가장 최적화된 풀이는 양쪽 끝부터 시작해서 작은쪽부터 진행해 나가는 풀이
    • 작은쪽에서 부터 진행하므로, 반대쪽은 신경쓸 필요가 없다는 점을 이용하면 시간/공간 모두 상수로 풀 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int trap(vector<int>& arr) {
        int lmax = 0, rmax = 0, left = 0, right = arr.size()-1, ans = 0;
        while(left < right) {
            if(arr[left] < arr[right]) {
                ans += lmax - arr[left] > 0 ? lmax - arr[left] : 0;
                lmax = max(lmax, arr[left++]);
            } else {
                ans += rmax - arr[right] > 0 ? rmax - arr[right] : 0;
                rmax = max(rmax, arr[right--]);
            }
        }
        return ans;
    }
};