盛水最多的容器/接雨水-java动态规划

盛水最多的容器

题目描述

感觉对动态规划还是理解不够清楚，一开始想了半天还是全部遍历的方法，最好的方法其实是一次移动一个指针，height小的内移。

class Solution {
    public int maxArea(int[] height) {
        //值大的不动，值小的向内移动
        if(height.length < 2)return 0;
        int first = 0;
        int last = height.length-1;
        int cap = Math.min(height[first],height[last])*(last-first);
        int tmp;
        while(first != last){
            if(height[first] > height[last]){
                last -= 1;
                tmp = Math.min(height[first],height[last])*(last-first);
                if(tmp > cap)cap = tmp;
            }
            else{
                first += 1;
                tmp = Math.min(height[first],height[last])*(last-first);
                if(tmp > cap)cap = tmp;
            }
        }
        return cap;
    }
}

接雨水

class Solution:
    def trap(self, height: List[int]) -> int:
        # 边界条件
        if not height: return 0
        n = len(height)
        maxleft = [0] * n
        maxright = [0] * n
        ans = 0
        # 初始化
        maxleft[0] = height[0]
        maxright[n-1] = height[n-1]
        # 设置备忘录，分别存储左边和右边最高的柱子高度
        for i in range(1,n):
            maxleft[i] = max(height[i],maxleft[i-1])
        for j in range(n-2,-1,-1):
            maxright[j] = max(height[j],maxright[j+1])
        # 一趟遍历，比较每个位置可以存储多少水
        for i in range(n):
            if min(maxleft[i],maxright[i]) > height[i]:
                ans += min(maxleft[i],maxright[i]) - height[i]
        return ans

太妙了，就只计算我头顶有多少水，最后加起来就行了，简洁明了。

Donate