Container With Most Water
You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Notice that you may not slant the container.
example
https://gyazo.com/e70b2dc17895c69ac7b354522cc367b0
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
解法
時間計算量 O(N^2)となる下記を考えたがTLEになる code:sol1.go
func maxArea(height []int) int {
var ret int
for i := 0; i<len(height)-1; i++ {
var maxAmount int
for j := i+1; j<len(height); j++ {
maxHeight := lHeight
if heightj < maxHeight { maxHeight = heightj } amount := maxHeight * (j-i)
if maxAmount < amount { maxAmount = amount }
}
if ret < maxAmount { ret = maxAmount }
}
return ret
}
解説を読むと
時間計算量 O(N)
空間計算量 O(1)
となる解法が載っていたので解き直してみる。
変数がmaxHeight or j-iであり、j-iが最大のところから順に探索していく方法を採っている
code:sol2.go
func maxArea(height []int) int {
var maxAmount int
i, j := 0, len(height)-1
for {
if i >= j { break }
if heightj < maxHeight { maxHeight = heightj } amount := maxHeight * (j-i)
if maxAmount < amount { maxAmount = amount }
i += 1
} else {
j -= 1
}
}
return maxAmount
}