题目描述：
给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例：
输入: [1,8,6,2,5,4,8,3,7] 输出: 49
题目难度：中等
分析：
可以简化题目的意思，其实就是确定两点坐标，然后根据坐标的值求得矩形的面积，找到最大的一个矩形即可。
解法一：暴力法
通过双层for循环，挨个求出每个矩形的面积即可，代码如下：
class Solution { public int maxArea(int[] height) { // 定义最大面积 int max = 0; int length = height.length; if (length < 2) { // 如果数组长度小于2直接返回0 return 0; } else if (length == 2) { // 如果数组长度等于2，直接返回较小的元素值即可，因为间隔为1，所以不需要计算面积 return Math.min(height[0], height[1]); } else { // 剩下就是长度超过2的情况，需要双层for遍历数组 for (int i = 0; i < length; i++) { for (int j = 1; j < length; j++) { // x 为两个下标直接的间隔长度，就是横坐标的间隔 int x = j - i; // y 为高度，因该取较小的那个 int y = Math.min(height[i], height[j]); // 计算x * y，即矩形面积，并和当前的最大面积比较，即可获得每次的最大面积 max = Math.max(max, x * y); } } } return max; } }
小结：
时间复杂度为O ( n 2 ) ，因为双层for循环很慢，时间复杂度为指数增长。
解法二：双指针法
由题意可知，矩形的面积和长高有关，那么在x轴上两点坐标相距越远，那么矩形的面积相对来说就会越大（这里只是理论数据），那么我们用双指针，一前一后，一遍扫描即可，最重要的就是怎么控制指针的移动逻辑，其实很简单，因为我们要最大面积，所以每次结束循环前保留左指针和右指针中最大（高度）的那一方，然后把较小的一方向另一方靠近即可。代码如下：
class Solution { public int maxArea(int[] height) { // 前半段同上 int max = 0; int length = height.length; int left = 0, right = length - 1; if (length < 2) { return 0; } else if (length == 2) { return Math.min(height[0], height[1]); } else { // 当左指针小于右指针的时候一直循环即可 while (left < right) { // 定义一个临时变量，来存储当前循环下的矩形面积 int temp = (right - left) * Math.min(height[left], height[right]); // 最大值面积和临时变量取较大值，即是每次循环完以后的最大值面积 max = Math.max(max, temp); /* 保留较大的指针位置不变，把较小的指针向对方靠近， 这里可能会出现相等的情况，其实这种情况不需要特殊处理，不管保留哪个都是可以的 */ if (height[left] < height[right]) { left++; } else { right--; } } } return max; } }
小结：
时间复杂度为O(n)，仅需要一次扫描即可。
总结：
暴力法简单粗暴，效率低下。双指针在数组操作中是比较常见的一个方法，以后会用到很多次。虽然在java中没有指针的概念，不过算法不分语言，常用的解题算法都需要掌握，遇到同类问题需要快速想到这种解法。
