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.
1 遍历的时候以width为变量
2 L指向左边,R指向右边,如果height[L]<height[R], 如果移动高的那个,也就是左移R,有以下情况:
(1)左移后,height[R]<height[L],则容器变小
(2)左移后,height[R]>height[L],则容器也变小
(3)左移后,height[R]=height[L],因为底变短了,则容器也变小
所以移动矮的那个指针才有用
1 基本思路是双指针,每一次遍历都更新water数,对于左右指针,每次移动矮的那个,木桶原理