LeetCode0011.盛最多水的容器Go语言AC笔记

时间复杂度：O(n)

第一反应是动态规划，再一想不应该那么复杂。

用双指针就可以很好地解决这个问题，时间复杂度只需O(n)。但问题是应该如何让指针移动呢？

仔细想想，容器的高度由较短垂线决定（这就是大名鼎鼎的木桶效应），所以我们的目标是找到尽量高的垂线，所以每次都比较两个垂线高度，让指向较短的那条垂线指针移动，然后记录下能容下的体积与最大值比较，如果超过最大值就更新，否则继续移动指针，直至两指针碰面返回最大值。

func maxArea(height []int) int {
    start,end,max:=0,len(height)-1,0//左右指针和最大值
    for startmax {
            max=temp
        }
    }
    return max
}

未来看到数组题如果有要求时间复杂度为O(n)，一定要想到双指针算法，并且确定好指针应该如何移动。