题目主要信息

1、给出一个数组，表示点的高度

2、找出最大的两条线所组成的容器的大小

方法一:双指针

具体方法

我们设两个指针i，j，指向的线高度分别为h[i], h[j]，因此我们可以将面积S表示出来如下图所示 而在每种状态下，无论长板或短板向中间收窄一格，都会导致水槽宽度-1：

• 若向内移动短板，水槽的短板可能变大，因此面积可能增加
• 若向内移动长板，水槽的短板不会变大，面积只可能减小 因此，循环每轮将短板向内移动一个，并更新面积最大值，直到两个指针相遇，即可得到最大值。

正确性证明

若暴力枚举，水槽两板围成面积 S(i,j)的状态总数为 C(n,2)。

假设状态 S(i,j)下 h[i]<h[j]，在向内移动短板至 S(i+1,j)，则相当于消去了 S(i,j−1),S(i, j - 2), ... ,S(i,i+1) 状态集合。而所有消去状态的面积一定都小于当前面积（即 <S(i,j）），因为这些状态：

• 短板高度：相比 S(i,j)相同或更短（即 ≤h[i]）；

• 底边宽度：相比 S(i,j)更短；

因此，每轮向内移动短板，所有消去的状态都 不会导致面积最大值丢失 ，证毕。

Java代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param height int整型一维数组 
     * @return int整型
     */
    public int maxArea (int[] height) {
        // write code here
        int l = 0, r = height.length-1;
        int ans = 0;
        while(l<r){
            int area = Math.min(height[l], height[r]) * (r-l);
            ans = Math.max(area, ans);
            if(height[l] <= height[r]){  //左侧为短边，移动短边
                l++;
            } else{  //右侧为短边，移动短边
                r--;
            }
            
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：$O(N)O(N)$，双指针遍历一次次底边长度N
• 空间复杂度：$O(1)O(1)$，常数额外空间

方法二：双指针+内部优化

具体方法

在双指针方法中，虽然时间复杂度为$O(N)O(N)$，但是每次移动都需要一次比较，我们可以进行优化，减少比较的次数，这里我们考虑到，如果向内移动时，如果短边的长度变短，那么移动后的面积一定小于移动前的面积，就可以不进行比较，知道移动后的面积大于移动前的面积。

Java代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param height int整型一维数组 
     * @return int整型
     */
    public int maxArea (int[] height) {
        // write code here
        int l = 0, r = height.length-1;
        int ans = 0;
        while(l<r){
            int area = Math.min(height[l], height[r]) * (r-l);
            int h = Math.min(height[l], height[r]);
            ans = Math.max(area, ans);
            while(height[l]<=h && l<r){  //当新短边大于原短边时停止
                l++;
            }
            while(height[r]<=h && l<r){  //当新短边大于原短边时停止
                r--;
            }
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：$O(N)O(N)$，双指针遍历一次次底边长度N
• 空间复杂度：$O(1)O(1)$，常数额外空间