题解 | #接雨水问题#

接雨水问题

https://www.nowcoder.com/practice/31c1aed01b394f0b8b7734de0324e00f

直接用快慢指针轻松解决(慢指针i;快指针j),避免用while...
public class Solution {
    public long maxWater(int[] height) {
        if (height.length <= 2)
        return 0;
        int n = height.length,res = 0;
        for (int i = 1; i < n - 1; i++) {
            int l_max = 0, r_max = 0;
            // 找右边最高的bar;
            for (int j = i; j < n; j++)
                r_max = Math.max(r_max, height[j]);
            // 找左边最高的bar;
            for (int j = i; j >= 0; j--)
                l_max = Math.max(l_max, height[j]);
            // (注意:如果自己就是最高的话,
            // l_max / r_max == height[i])
            res += Math.min(l_max, r_max) - height[i];
        }
        return res;
    }

}

全部评论

相关推荐

点赞 评论 收藏
分享
程序员小白条:找的太晚,别人都是大三实习,然后大四秋招春招的,你大四下了才去实习,晚1年
点赞 评论 收藏
分享
练习生懒羊羊:开飞机把这个公司创飞吧
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务