Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Trapping Rain Water

Leetcode algorithms 第 42 题:Trapping Rain Water 。

题目

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example, 
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

解答

求若干柱子能够装下的水的数量。由于装的水的数量是有两根柱子中较短的一根决定,可以先选择一根最长的柱子作为基准,然后只需要考虑另一端的柱子。由于最长的柱子一般在中间,其两边都可能会有柱子,需要对左右两边同样进行分析处理。

考虑左边的情况,从最左边开始向最长的柱子扫描,如果当前柱子比之前的柱子都高,说明如果后面的柱子比当前柱子低,则其能够装二者高度差的水,否则,当前柱子也是以之前某根较高的柱子为边界装二者高度差的水。右边的情况类似。

具体代码如下:

class Solution {
public:
    int trap(int A[], int n) {
        if (n <= 1) return 0;
        
        int mxid = 0; //最高柱子的位置
        for (int i = 1; i < n; i++)
            if (A[i] > A[mxid]) 
                mxid = i;
        
        int ans = 0; 
        for (int i = 1, mx = A[0]; i < mxid; i++)//左边情况
        {
            if (A[i] > mx) //当前最高的
                mx = A[i];
            else
                ans += mx - A[i]; //不是最高的,则可以装与最高柱子高度差的水
        }
        
        for (int i = n-2, mx = A[n-1]; i > mxid; i--)//右边情况
        {
            if (A[i] > mx) 
                mx = A[i];
            else
                ans += mx - A[i];
        }
        
        return ans;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论