介紹雙指標的奧妙

題目連結: 11. Container With Most Water

題目描述:

給定一個非負整數的陣列 height，陣列中的每個數字 height[i] 代表了在座標 (i, height[i]) 處的一條垂直線，請找出其中的兩條線，使得它們與 x 軸共同構成的容器可以容納最多的水。

核心規則:
容器的容量由兩條線中 較短 的那條以及兩條線之間的距離所決定，找出所有( i, j ) 組合中，能得到的最大面積。
公式: 面積 = min(height[i], height[j]) * (j - i)

Python

最直觀的方法是使用巢狀迴圈去遍歷滿足(i,j)的組合
如下:

class Solution:
    def maxArea(self, height: List[int]) -> int:
        n = len(height)
        max_container = 0
        for i in range(n):
            for j in range(i+1,n):
                temp = min(height[i],height[j])*(j-i)
                max_container = max(max_container,temp)
        return max_container

• 此方法的時間複雜度是O(n^2)，雖然可以執行，不過送入Leetcode系統複查會顯示Time Limit Exceeded。
• 當n很大時，執行時間會非常慢。
• 空間複雜度O(1)，只使用變數所以是常數空間。

因此，雙指標 就派上用場了

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left = 0
        right = len(height)-1
        max_container = 0
        while left<right:
            curr = min(height[left],height[right])*(right-left)
            max_container = max(curr,max_container)
            if height[left]<height[right]:
                left+=1
            else:
                right-=1
        return max_container

• 先建立兩個指向陣列頭、尾的指針
• 重點是while迴圈的執行，該移動哪個指針?
• 我們的面積由 寬度 * 短板高度 決定。當我們把指針向內移動時，寬度必定會變小。
• 想讓面積變大勢必找出更高的短板來彌補寬度的損失。
• 如果移動較高的柱子，新的短版只會小於等於目前的短版，面積不會變大。
• 因此要移動較短的短版來尋找大於它的短版
• 迴圈結束，返回max_container。
  由於left、right都只會遍歷一次陣列，所以時間複雜度是O(n)，空間複雜度是O(1)。

這樣子有更了解演算法的重要性了嘛!
今天就介紹到這邊，有問題都可以留言
下回見!