美文网首页
42. Trapping Rain Water

42. Trapping Rain Water

作者: gpfworld | 来源:发表于2018-12-11 15:34 被阅读0次

    题目描述:

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

    解决方法:

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

    optim_code(c++):

    int trap(vector<int>& height)
    {
        int left = 0, right = height.size() - 1;
        int ans = 0;
        int left_max = 0, right_max = 0;
        while (left < right) {
            if (height[left] < height[right]) {
                height[left] >= left_max ? (left_max = height[left]) : ans += (left_max - height[left]);
                ++left;
            }
            else {
                height[right] >= right_max ? (right_max = height[right]) : ans += (right_max - height[right]);
                --right;
            }
        }
        return ans;
    }
    

    心得:

    Approach 1: Brute force
    将问题分割的思想,并不是一次一个部分trap的大小,而是进行分解,一次就求解一个上面trap的大小。在算左侧最大时,会把本身的值算进去。因为trap必须比本身大。右侧同理。
    Approach 2: Dynamic Programming
    方法中依次找出左侧或者右侧最大的值的思想很好,每次都是max(height[i], left_max[i - 1]),其实就是找到了左侧的最大值。右侧同理。

    0 1 2 3 4 5 6 7 8 9 10 11
    left_max 0 1 1 2 2 2 2 3 3 3 3 3
    right_max 3 3 3 3 3 3 3 3 2 2 2 1

    Approach 3: Using stacks
    思路奇特,较难理解
    Approach 4: Using 2 pointers
    需观察算法特点,在approach2的基础基础上优化

    相关文章

      网友评论

          本文标题:42. Trapping Rain Water

          本文链接:https://www.haomeiwen.com/subject/resshqtx.html