iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 27
1
自我挑戰組

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

【從面試題學邏輯-27】首次體驗到有效率沒效率的題目(leetcode 11. Container With Most Water)

題目:
請寫一個方法,輸入一個int陣列,陣列內的數字代表牆的高度,請輸出兩道牆之間最多可以存的水量

點我前往LeetCode題目


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

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


由於時間關係,最後兩部分的份量實在分配不均/images/emoticon/emoticon06.gif
最後幾天我們來看看一些比較有效率的解法吧

這一題有點歷史意義啊(?),剛好是個人在LeetCode上的第一題,當然剛開始碰都是暴力解,像這個

class Solution {
    public int maxArea(int[] height) {
        int ans=0;
        for(int i = 0;i<height.length;i++) {
            for(int j=i+1;j<height.length;j++) {
                ans = Math.max(ans, Math.min(height[i],height[j])*(j-i));
            }
        }
        return ans;
    }
}

這就是第一次解題的第一個解,想當然這種暴力解只會得到這種結果

真的不是普通的慢诶! /images/emoticon/emoticon04.gif

雖然過是過了,但這種解法就是真的沒效率
所以我們來思考一下這題要怎麼處理比較快吧

首先,題目提到的蓄水區應該是下面這樣

比較低的牆乘上兩牆間距(應該不用多解釋吧~?)

再來我們要來個重點:

如果寬逐漸縮小,那要什麼情況下容水量才會更大?

題目中我們是找兩道牆,而寬最多就是0~height.length,我們之後找的寬都不會再更大。所以寬只會逐漸縮小

那寬縮小容水量要更大的話呢?就是高要增加才有可能做到

所以我們可以在height最左及最右設定兩根旗子,比較矮的那根旗子會逐漸往內靠,來試著找到更高的牆,這樣或許就能找到更多容水量(像下面GIF)

因此我們可以得到這段程式碼:

class Solution {
    public int maxArea(int[] height) {
        int sum=0;
        int left=0, right=height.length-1;
        while(left!=right) {
            sum = Math.max(Math.min(height[left],height[right])*(right-left) , sum);
            if(height[left]>height[right]) right--;
            else left++;
        }
        return sum;
    }
}

相較前面那段兩個迴圈的程式碼,這次我們只要一個迴圈就能搞定

所以就快非常多啦~


上一篇
【從面試題學邏輯-26】在不使用遞迴的情況下後序走訪二元樹(leetcode 145. Binary Tree Postorder Traversal)
下一篇
【從面試題學邏輯-28】路面坑洞坑坑巴巴兼積大水(leetcode 42. Trapping Rain Water)
系列文
新手也能學!一起從面試題理解程式邏輯!30

尚未有邦友留言

立即登入留言