3種方法： 計算接最多的雨水

文章目錄

• • 題目
  • 解法一（暴力法）
  • 解法二（動态規劃）
  • 解法三（雙指針法）

題目

給定 n 個非負整數表示每個寬度為 1 的柱子的高度圖，計算按此排列的柱子，下雨之後能接多少雨水。

上面是由數組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖，在這種情況下，可以接 6 個機關的雨水（藍色部分表示雨水）。 感謝 Marcos 貢獻此圖。

示例:

輸入: [0,1,0,2,1,0,1,3,2,1,2,1]

輸出: 6

解法一（暴力法）

思路：在每個位置，分别向左和向右找雨水的邊界，進而得到雨水在目前位置的深度，累加每個位置的深度即為所求。

1. 對整個區域的每個位置進行計算
2. 分别向左和向右尋找邊界值，然後取得兩個邊界值的最小值，作為目前水量高度
3. 累加所有坐标的水量

• 時間複雜度：O(n2)
• 空間複雜度：O(1)

//author： [email protected]
int trap(int* height, int heightSize){
    int cnt = 0, rightIdx, rightVal, leftIdx, leftVal;
    for(int k=0; k<heightSize; k++){
        rightIdx = k;
        rightVal = height[k];
        leftIdx = k;
        leftVal = height[k];
        for(int i=0; i<k; i++){//向左找最大值
            if(height[i] > leftVal){
                leftVal = height[i];
                leftIdx = i;
            }
        }
        for(int i=k+1; i<heightSize; i++){//向右找最大值
            if(height[i] > rightVal){
                rightVal = height[i];
                rightIdx = i;
            }
        }
        cnt += (leftVal> rightVal?rightVal:leftVal) - height[k];
    }
    return cnt;
}
           

解法二（動态規劃）

思路：基于解法一進行優化，解法一每個位置都要周遊整個區間來尋找左右最大值，可以基于動态規劃的思想，分别從左右兩邊開始尋找目前位置的左右方向的最大值，是以執行時間從N2變為2N。

1. 申請臨時空間，分别用于存儲目前坐标，左右兩邊的最大值
2. 從左邊開始向右尋找每個左邊能看到的最大值，右邊同理
3. 累加所有坐标的水量

• 時間複雜度：O(n)
• 空間複雜度：O(n)

//author： [email protected]
int trap(int* height, int heightSize){
    if(heightSize == 0) return 0;
    int cnt = 0, *leftMax, *rightMax;//臨時變量保持各位置的左右最大值
    leftMax = (int *)malloc(sizeof(int)*heightSize);
    rightMax = (int *)malloc(sizeof(int)*heightSize);
    memset(leftMax,0,heightSize);
    memset(rightMax,0,heightSize);
    leftMax[0] = height[0];
    for(int i=1;i<heightSize;i++){//左邊最大值
        leftMax[i] = leftMax[i-1] > height[i]?leftMax[i-1]:height[i];
    }
    rightMax[heightSize - 1] = height[heightSize - 1];
    for(int i=heightSize - 2;i>=0;i--){//右邊最大值
        rightMax[i] = rightMax[i+1] > height[i]?rightMax[i+1]:height[i];
    }
    for(int i=0; i<heightSize; i++){
        cnt += (leftMax[i]> rightMax[i]?rightMax[i]:leftMax[i]) - height[i];
    }
    free(leftMax)
    free(rightMax)    
    return cnt;
}
           

解法三（雙指針法）

思路：基于解法二進行優化，由于求出一個位置左右兩邊最大值後，僅使用其中較小的值，并舍棄較大一邊的值，是以不必找到每個位置左右兩邊的最大值，而是隻要找到左右兩邊最大值中較小的值即可。

使用兩個指針，來标志左右兩邊的位置值，并不斷向中間遞進，如果坐标值大則右邊指針一直向左邊移動，反之亦然，每個位置計算時候都是左右兩邊的最大值中的較小值。

1. 左邊最大值從左向右移動，右邊最大值從右向左移動，左右兩個指針相遇後，循環結束
2. 左邊值如果大于右邊，則計算右邊目前儲水量，并且右邊指針向左移動，反之同理
3. 分别記錄兩邊的最大值，用于計算每個位置的儲水量，儲水量等于最大值減去目前值

• 時間複雜度：O(n)
• 空間複雜度：O(1)

//author： [email protected]
int trap(int* height, int heightSize){
    int cnt = 0, rightIdx = heightSize - 1, rightVal = 0, leftIdx = 0, leftVal = 0;
    while(leftIdx <= rightIdx){
        if(leftVal < rightVal){//最大值在右邊
            if(height[leftIdx] > leftVal){//存儲左邊新的最大值
                leftVal = height[leftIdx];
            }
            else{//基于左邊值計算儲水量
                cnt += leftVal - height[leftIdx];
            }
            leftIdx ++;
        }
        else{
            if(height[rightIdx] > rightVal){//記錄右邊最大值
                rightVal = height[rightIdx];
            }
            else{
                cnt += rightVal - height[rightIdx];
                rightIdx --;
            }
        }
    }
    return cnt;
}