当前位置:网站首页>The container with the most water

The container with the most water

2020-11-08 10:30:30 osc_1ajf1srl

      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 .

版权声明
本文为[osc_1ajf1srl]所创,转载请带上原文链接,感谢