iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 28
1
自我挑戰組

新手也能學!一起從面試題理解程式邏輯!系列 第 28

【從面試題學邏輯-28】路面坑洞坑坑巴巴兼積大水(leetcode 42. Trapping Rain Water)

題目:
請寫一個方法,輸入一個int陣列,陣列內的數字代表路面高度,請輸出路上最多可以積多少水

反正就是路上的坑洞可以積多少水XD

點我前往LeetCode題目


那在開始前不乏提醒一下此系列的固定提醒:

這是一系列逐漸帶入解題的文章,難度會隨著進度增加,若還沒有讀過前面的文章,建議先從最前面開始來逐漸練習解題喔!


今天這題是昨天題目的進階題目,我們會用到昨天的左右旗子概念,建議大家先看看昨天的題目

今天這題的集水區應該要變成下圖這樣(用文字說明太抽象所以改用圖片)

左邊是上一題的,右邊是今天題目的。

上一題的概念是每道牆壁中間都有1的空間,也就是假設牆壁不占空間,而且最後只有兩道牆壁會出現。而今天這題的牆壁(地板)則是佔了整格空間,外加每道牆壁都會出現,不是昨天那種N取2出現

那昨天的插旗子要怎麼套用到今天題目呢?大家要知道用旗子算集水區的核心概念就是:
比較矮的牆往另一邊掃過去,一定會對應到更高的牆,所以要移動的旗子是比較矮的牆那根

因為如果是比較高的牆,移過去沒對到更高的牆就爆炸啦!

再來移動的同時我們也要記錄牆的高度,來讓我們去算會積多少水。而如果遇到更高的牆,就把牆壁的高度設成更高的高度,如果沒有,就把高度減掉地板高度,就能拿到水量

具體運作像下面這張圖(上面都很抽象,所以我們還是看GIF吧,注意牆高的變化)

所以我們可以得到下面這段程式碼

class Solution {
    public int trap(int[] height) {
        if(height.length==0) return 0;
        int left=0, right=height.length-1, size=0, leftMax=height[0], rightMax=height[height.length-1];
        while(left<right) {
            if(leftMax>rightMax){
                rightMax=Math.max(rightMax,height[right-1]);
                size+=rightMax-height[--right];
            } else {
                leftMax=Math.max(leftMax,height[left+1]);
                size+=leftMax-height[++left];
            }
        }
        return size;
    }
}
if(height.length==0) return 0;

這段就是避免有人傳空的東西進來

int left=0, right=height.length-1, size=0, leftMax=height[0], rightMax=height[height.length-1];

leftright就是旗子的位置,而leftMaxrightMax,就是左右旗子掃過的最高牆壁高度

while(left<right) {
    if(leftMax>rightMax){
        rightMax=Math.max(rightMax,height[right-1]);
        size+=rightMax-height[--right];
    } else {
        leftMax=Math.max(leftMax,height[left+1]);
        size+=leftMax-height[++left];
    }
}

接著,我們移動牆壁高度比較低的那根旗子,如果新掃到的牆壁高度比較高,就更新牆壁高度,如果沒有,就算水量。

如此一來就能算出坑洞的集水量


上一篇
【從面試題學邏輯-27】首次體驗到有效率沒效率的題目(leetcode 11. Container With Most Water)
下一篇
【從面試題學邏輯-29】如何寫出1A2B猜數字遊戲?(leetcode 299. Bulls and Cows)
系列文
新手也能學!一起從面試題理解程式邏輯!30

尚未有邦友留言

立即登入留言