Leetcode-11 Container With Most Water

xiaoxiao2021-02-28  5

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

func maxArea(height []int) int { m:=0 len:=len(height) for i,j:=0,len-1 ; i<len && j>=0 ; { area:=(j-i)*min(height[i],height[j]) m=max(m,area) if height[i] <= height[j]{ i++ }else{ j-- } } return m } func min(i int ,j int ) int { if i<=j { return i; } return j } func max(i int ,j int ) int { if i>=j { return i; } return j } 最好不要暴力搜索,暴力搜索的时间级别在O(n2),利用贪心算法的思路,可以优化到O(n)左右,基本思路是在每次循环的时候去掉左右最矮的边取的局部最优解,然后与max比较,最后的结果就是全局最优解

转载请注明原文地址: https://www.6miu.com/read-450315.html