iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 27
1
Software Development

LeetCode30系列 第 27

[LeetCode30] Day27 - 42. Trapping Rain Water

題目

有一個array,size為n,儲存的值皆>=0,值代表那格的海拔高度,這樣會形成很多凹槽,如果下雨了,會積多少雨水呢?

以下圖為例子,答案是6
https://ithelp.ithome.com.tw/upload/images/20201012/20129147Xl9lZ0OoHn.png

解法

用2個pointer,iji先固定,j往後,當j的海拔高大於或等於i的海拔高,代表有可能有凹槽,另外一個情況是走到最後了,都是i大於j,但也要處理一次。
e.g.
https://ithelp.ithome.com.tw/upload/images/20201012/20129147R45yr6jcEI.png

接著就先算出最高是多少,所以ij取小的,然後用一個pointer反走回去直到i,然後計算會積多少水。
這裡不能直接用i往前走到j,從上面的例子,應該看的出來會發生什麼事。

Code

class Solution {
public:
    int trap(vector<int>& height) {
        int trap_water = 0;
        int i = 0;
        int j = 1;
        while(j < height.size()){
             if (height[i] <= height[j] || j == height.size() - 1) {
                int level = min(height[i], height[j]);
                int k = j - 1;
                while (k != i) {
                    level = max(height[k], level);
                    trap_water += level - height[k--];
                }
                i = j;
            }
            
            j++;
        }
        return trap_water;
    }
};

https://ithelp.ithome.com.tw/upload/images/20201012/201291473Pk6Ior5W0.png


上一篇
[LeetCode30] Day26 - 1106. Parsing A Boolean Expression
下一篇
[LeetCode30] Day28 - 65. Valid Number
系列文
LeetCode3030
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言