The container with the most water

      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 .