0011.Container With Most Water

題目

題目大意

解題思路

利用雙指針, 找出最小的高並乘上兩指針距離, 得出面積 當左指針高度比右指針高度高時, 將右指針往左移, 反之將左指針往右移.

Big O

• 時間複雜 : O(n)
• 空間複雜 : O(1)

來源

• https://leetcode.com/problems/container-with-most-water/description/
• https://leetcode.cn/problems/container-with-most-water/description/

解答

https://github.com/kimi0230/LeetcodeGolang/blob/master/Leetcode/0011.Container-With-Most-Water/main.go

package containerwithmostwater

// 時間複雜 O(n), 空間複雜 O(1)
func maxArea(height []int) int {
    left, right := 0, len(height)-1
    result := 0
    for left < right {
        tmp := (right - left) * min(height[left], height[right])
        result = max(result, tmp)
        if height[left] > height[right] {
            right--
        } else {
            left++
        }
    }
    return result
}

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
}

Benchmark