11. Container With Most Water

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

**Note: **You may not slant the container and n is at least 2.

The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

题目

一个数组，画在坐标系里，索引为横轴，值为纵轴。求两个值，使以这两个值的柱子与横轴组成的容器能乘最多的水。
什么意思呢？
就是求两个数，使得（索引差×两个数的最小值）最大，返回这个最大值。

思路

假设这个区间就是数组收尾组合而成的，[0,n-1]，此时我们需要考虑中间有没有容积更大的组合，方法就是移动短的那个边，看看有没有比他长的边存在，因为往里移动x轴的边减小了，要想容积变大，必须竖着的边要更长才行。左边移动完，移动右边，都遍历完，取容积最大值就可以了

代码

         int res=0;
         int left=0;
         int right=height.length-1;
         while (left<right) {
         //最大值为：
         res = Math.max(res, Math.min(height[left], height[right]) * (right - left));
         //如果左边低，则从左往右找一条高于left的边，这样有可能容积更大。
         if (height[left]<height[right]) {
            int tmp=left;
            while (tmp<right&&height[tmp]<=height[left]) {
                tmp++;
            }
            //while循环停止时就是找到了这个边,循环算一下
            left=tmp;
        }else {
            int tmp=right;
            while (tmp>left&&height[tmp]<=height[right]) {
                tmp--;
            }
            //while循环停止时就是找到了这个边，循环算一下
            right=tmp;
        }
         }
        return res;