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

interview
array
leetcode
hard

(Lê Trần Đạt) #1

Đề bài:

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


Topic tổng hợp các video chia sẻ về interview của ltd
(A Nguyễn Văn) #2

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;
    }
};

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?