Giải bài 42 trapping rain water O(N)

[ltd (Lê Trần Đạt)]

Đề bài:

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

Bài giải

Code Python

class Solution(object):
    def trap(self, h):
        """
        :type h: List[int]
        :rtype: int
        """
        if not h: return 0
        i, j = 0, len(h) - 1
        max_left = h[i]
        max_right = h[j]
        water = 0
        while i < j:
            if max_left <= max_right:
                water += max_left - h[i]
                i += 1
                max_left = max(max_left, h[i])
            else:
                water += max_right - h[j]
                j -= 1
                max_right = max(max_right, h[j])
        return water

Nhờ các bạn giải với ngôn ngữ khác

[a_nguyen_van (A Nguyễn Văn)]

C++ code

class Solution {
public:
    int trap(vector<int>& a) {
        if(a.size() == 0) return 0;
        int i = 0, j = a.size() - 1;
        int tot = 0, L = a[i], R = a[j];
        while(i < j){
            if(L <= R) {
                ++i;
                L = max(L, a[i]);
                tot += L - a[i];
            }
            else {
                --j;
                R = max(R, a[j]);
                tot += R - a[j];
            }
        }
        return tot;
    }
};

[japananh (Trần Nhật Anh)]

Javascript

var trap = function(h) {
    if (h.length < 3) return 0;
    
    let [i, j] = [0, h.length - 1];
    let [maxLeft, maxRight] = [h[i], h[j]];
    let water = 0;
                                 
    while (i < j) {
        if (maxLeft <= maxRight) {
            water += maxLeft - h[i];
            ++i;
            maxLeft = Math.max(maxLeft, h[i]);
        } else {
            water += maxRight - h[j];
            --j;
            maxRight = Math.max(maxRight, h[j]);
        }
    }
    
    return water;
};