# The container with the most water

2020-11-08 10:30:30

Original published in ：

Today is the weekend , Look at G An interview question from the company ：

seek max{|i-j|*min{a[i], a[j]}} Value , among a It's an array of positive integers ,i and j The interval is [0, n-1].

This is actually leetcode Medium “ The container with the most water ”, as follows ：

Lu xun said ： Violence can solve all problems .

Hushi said ： The problem that violence can solve , It's not a problem .

because i and j The possibility of a limited combination , So the brute force algorithm gets the result , But failed to pass the interview .

Do you use dynamic programming ？ It seems that dynamic planning is not good either .

We can use double pointers , Point to the head and the tail respectively , Calculate the water content . And search in the middle , Try to find out more possibilities for holding water .

The barrel theory tells us ： For two definite water baffles , The amount of water is determined by the short board .

therefore , When searching in the middle , Move the pointer from the short board to the middle , It is possible to produce a greater water holding value .

This is a central conclusion .

As for the code , It's simple , Take a look ：

``````func maxArea(a []int) int {
n := len(a)

if n < 2 {
return 0
}

if n == 2 {
return min(a[1], a[0])
}

max := min(a[n - 1], a[0]) * (n - 1)

i := 0
j := n - 1

for i < j  {
if a[i] < a[j] {
i++
}else {
j--
}

area := min(a[i], a[j]) * (j - i)
if area > max {
max = area
}
}

return max
}

func min(x, y int) int {
if x < y {
return x
}

return y
}``````

result ：

The algorithm can pass the interview normally , I wish you all the best offer.

Have a nice weekend .