Leetcode——接雨水

題目：

一行一行的算所接雨水量

代碼：

class Solution {
    public int trap(int[] height) {
        int res=0;
        int temp=0;
        int max=0;
        int flag=0;
        //找到最高的值
        for(int i=0;i<height.length;i++){
            if(height[i]>max)
                max=height[i];
        }
        //分層進行計算
        for(int i=1;i<=max;i++){
            flag=0;
            temp=0;
            for(int j=0;j<height.length;j++){
                //找到第一個大于所求層數的值，進行标注
                if(flag==0 && height[j]>=i){
                    flag=1;
                    continue;
                }
                //隻有标注過後才可以temp++
                if(flag==1 && height[j]<i){
                    temp++;
                    continue;
                }
                //當再次遇到超過目标層數的值後，可以再res中加上temp
                if(flag==1 && height[j]>=i){
                    res+=temp;
                    temp=0;
                }
            }
        }
        return res;
    }
}
           

時間複雜度是O(n*max)

可能是這個辦法有點取巧了，在leetcode中是會逾時的

這時候我們就需要更有效的方法

我嘗試了按列求所接雨水

代碼：

class Solution {
    public int trap(int[] height) {
        int res=0;
        int left_max=0;
        int right_max=0;
        for(int i=1;i<height.length-1;i++){
            left_max=0;
            right_max=0;
            //找出目前列左側的最高峰
            for(int j=0;j<i;j++){
                if(height[j]>left_max)
                    left_max=height[j];
            }
            //找出目前列右側的最高峰
            for(int j=i+1;j<height.length;j++){
                if(height[j]>right_max)
                    right_max=height[j];
            }
            //隻有兩邊的最大值都比目前列的值大時，才能進行加法操作
            if(height[i]<Math.min(left_max,right_max))
                res=res+Math.min(left_max,right_max)-height[i];
        }
        return res;
    }
}
           

時間複雜度O（n^2）

結果：