兩指針技術

Go 中用兩個指標最大化容器區域

在使用陣列或列表的演算法中，兩指標技術因其效率而脫穎而出。 在本文中，我們將其應用於經典的「裝有最多水的容器」問題，該問題尋求圖形上兩條垂直線之間的最大面積。

問題描述

給定一個表示垂直線高度的非負整數數組，找出與 x 軸一起形成面積最大的容器的一對線。

範例

考慮數組height = [1, 8, 6, 2, 5, 4, 8, 3, 7]。 目標是確定哪兩條線產生最大面積。

雙指針技術

該技術使用兩個指針，一個位於數組的開頭，一個位於數組的末尾，將它們迭代地移向中心以找到最佳解決方案。

一步一步

1. 啟動：

   • maxArea 初始化為 0，儲存迄今為止找到的最大區域。
   • 兩個指針，l（左）和r（右），分別位於數組的開頭和結尾。

2. 迭代：

   • 只要 l 小於 r，循環就會繼續。
   • l 和 r 中的線之間的面積計算為 min(height[l], height[r]) * (r - l)。
   如果計算的面積較大，
   • maxArea 會更新。

3. 指針移動：

   • 為了最佳化搜索，指向較小行的指標被移動：
     • 如果 height[l] < height[r]，則遞增 l。
     • 否則，遞減r。

4. 回傳：

   • 當l與r相交時，循環結束，maxArea包含最大面積。

詳細範例

讓我們來分析一下陣列height = [1, 8, 6, 2, 5, 4, 8, 3, 7]:

1. 啟動：

   • maxArea = 0
   • l = 0（高度 1），r = 8（高度 7）

2. 第一次迭代：

   • 區域：min(1, 7) * (8 - 0) = 8
   • maxArea = max(0, 8) = 8
   • 移動l（因為height[l] < height[r]）

3. 第二次迭代：

   • l = 1（高度 8），r = 8（高度 7）
   • 區域：min(8, 7) * (8 - 1) = 49
   • maxArea = max(8, 49) = 49
   • 移動r

...依此類推，重複這個過程，直到雙手相遇。

最終結果將是maxArea = 49。

去解決

依照 Go 程式碼實作此技術：

package maxarea

func maxArea(height []int) int {
    maxArea := 0
    l, r := 0, len(height)-1

    for l < r {
        area := min(height[l], height[r]) * (r - l)
        maxArea = max(maxArea, area)
        if height[l] < height[r] {
            l++
        } else {
            r--
        }
    }
    return maxArea
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

結論

雙指標技術為涉及陣列的問題提供了有效的解決方案。 在「盛水最多的容器」的情況下，它保證了線性時間複雜度，使其成為一種理想的方法。

以上是兩指針技術的詳細內容。更多資訊請關注PHP中文網其他相關文章！