(java)leetcode-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.

解题思路：

这道题意思大概是，给定一个数组，数组的下标表示x坐标，下标所对应的值表示y坐标，可以看成在x坐标位置有一块高度为height[x]的木板，然后找到两块木板，这两块木板跟x轴所围成的容器能够容纳最多的水。

首先容纳水这种东西不应该是体积吗为毛要求面积...

所以，就是相当于找最大一个面积，宽是两个下标的距离，长是两个下标对应的数组的值的最小值。

所以我的想法就是，从距离最远的两个值开始，向中间遍历，直到两个坐标点重合。

假设左边的坐标点是left，右边的坐标点是right，由于选择的高度是两个中的最小值，所以当height[left]<height[right]时，只需要考虑left向右移动的情况，因为right向左移动的结果都只会比原来的小。反之亦然。

[java] view plain copy print ? public class Solution {      public int maxArea(int[] height)       {          int left = 0;int right = height.length -1;          int result = 0;          while(left != right)          {              int area = (right-left)*Math.min(height[left],height[right]);              result = Math.max(result, area);              if(height[left]<height[right])                  left++;              else                  right--;          }          return result;      }  }   public class Solution { public int maxArea(int[] height) { int left = 0;int right = height.length -1; int result = 0; while(left != right) { int area = (right-left)*Math.min(height[left],height[right]); result = Math.max(result, area); if(height[left]<height[right]) left++; else right--; } return result; } }