算法升级之路（七）-盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。
原题链接: 盛最多水的容器

解题思路：
这道题乍一看没什么思路，用暴力循环的话太麻烦了，要从第一个循环剩下的所有，第二个循环剩下的所有，第三个。。。
我也是看了答案之后才明白怎么算，其实很简单。

这个盛水的面积= min（height[i]，height[j]）*（j-i）；

从i=0 和j=heigh.length-1算起
在这个状态下只要挪动板子，（j-i）都是会变小

min（height[i]，height[j] 只有变大才有机会变大

由于求的是最小值，那么只有最小值变大，面积才有变大的可能。
所以每次挪动最小的板子，直到两个板子重合，就能得出最大面积。

代码

 public int maxArea(int[] height) {
        int area = 0;
        int front =0;
        int backend =height.length-1;
        while(front!=backend){
          int   current =Math.min(height[front],height[backend])*(backend-front);
          if(current>area){
              area = current;
          }
          if(height[front]<height[backend]){
              front++;
          }else{
              backend--;
          }
        }
        return area;


    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

这个算法让我有种我当年上高中事，做题做不出，老师一讲就听懂了的感觉，梦回高三。
我啥时候才能到这种水平呀