RBA的技术分享

题目:

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/container-with-most-water
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1]
输出：1

示例 3：

输入：height = [4,3,2,1,4]
输出：16

示例 4：

输入：height = [1,2,1]
输出：2

暴力解法

没得说,两层for循环. 枚举出所有可能的值. 依次比较,留下最大值.
代码看起来还算比较优美. 代码量很少.
不幸的是代码超时了.有部分 case 过不了.

class Solution {
    public int maxArea(int[] height) {
        int max = 0;
        for (int i =0;i<height.length-1;i++){
            for(int j=i+1;j< height.length;j++){
                max = Math.max(max,(j-i)*(Math.min(height[i],height[j])));
            }
        }
        return max;
    }
}

双指针-递归

双指针方法的证明:

假设最开始 , 长度为 n 的数组为: a[0] , a[1] , a[2] , a[3] , .... , a[n-2] , a[n-1]

• a[0] 为左边界;
• a[n-1] 为右边界;

假设 a[0] < a[n-1] ,

• 即左边界小. 此时如果 小的边界:a[0]保持不动 , 右指针此时在最右边.只能往左移动.
• 对于 i = 0时,所有的 j ( 0 < j <= n-1 ) 都会有 S(0,j) < S(0,n-1) ,此时换句话说: S(0,n-1)是以a[0]为左挡板的最大面积记录保持者 ,即得出: 只要已经记录下了: S(0,n-1)的值以备用后. 所有其它以 a[0]为左挡板的面积都不用计算了. (因为都不会大于此值). -
• a[0]本身处于最左边. 因此不可能作为右挡板. 因此有a[0]作为挡板的可能值记录一个S(0,n-1),即可. 其它都不用计算了. 再抽换个说法就是: 剩下就是只计算以 a[1],a[2], ... , a[n-1]这一堆可能的两两的挡板值的面积与之前的S(0,n-1)比较即可.
• 如上. 问题的规模从 n 转换为了新的n-1;

假设反过来. a[0] > a[n-1] , 证明方法相同. 即从右边往左边移动. 同时可以把最右边的 a[n-1] 给trim掉. 同时问题规模 -1

对于相等的情况: 实际一样. 相等的时候可以选任意一边的值为挡板. 同样移动另外一个得到的值都不会大于当前值.那仍然可以只计算当前值.

证毕.

问题的比较绕.或者是可能的坑的点在于一开始可能想歪,比如变成了有点贪心的算法的意味 . 比如用最两端的值作为初始值. 可能想到用贪心的方法.不断的往里面移动. 然后用可能的更大的值代替已经取到了 面积 S 值. 而这个过程中中间产生的面积值有可能不是最优的 . 从而让思路限入了僵局.

实际的整个过程仍然是与暴力方法一样在枚举所有的可能的值. 只是在枚举的过程中 把一些不可能作为最大值的或者在已经某个 S(i,j)值的时候. 有些值是不必要算的.这样来进一步的减少枚举的空间的范围.

class Solution {
    public int maxArea(int[] height) {
        return maxAreaR(height,0,height.length-1);
    }

    public int maxAreaR(int[] height,int l,int r){
        if(l >= r){
            return 0;
        }
        if(height[l] < height[r]){
            return Math.max(height[l] * ( r - l) , maxAreaR(height, l+1,r));
        }else{
            return Math.max(height[r] * ( r - l) , maxAreaR(height,l,r-1));
        }
    }

}

双指针-常规

上面的实现实际只是在进行证明的过程中比较容易往递归上走的写法. 实际与普通的双指针并无二致. 下面给出标准的双指针解法
还好, 解法仍然很简洁.

class Solution {
    public int maxArea(int[] height) {
        int max = 0;
        for(int i=0,j=height.length-1;i<j;){
            if(height[i] < height[j]){
                max = Math.max(max,height[i]*(j-i));
                i++;
            }else{
                max = Math.max(max,height[j] * (j-i));
                j--;
            }
        }
        return max;
    }
}

结语

三种代码都很简洁.但是复杂度却相关很远.