Leetcode-011-盛水最多的容器

Leecode-011Container With Most Water

思路：双指针

题目描述

在范围内找出两条直线（组成一个面积最大的区域也就是盛水的容积）

Solution：分三种情况分析

• 左指针对应高度 > 右指针对应高度 （结果：右指针左移，这样右指针才能找到比当前大的高度）
• 左指针对应高度 < 右指针对应高度 (结果：左指针右移，这样左指针才能找到比当前大的高度)
• 左指针对应高度 = 右指针对应高度 （结果： 左右指针同时移动一位 即右指针左移，左指针右移）

下面举例子说明：

首先用area记录下当前的最大盛水容积

我们采用[2,1,3,4] 作为举例

如下图所示：

• 首先left指针初始为0，right初始为最后一个元素
• 其次，在图中我们可以明显看出（无论怎么移动右指针，容积只会是变小的；只有移动left，容积才有可能变大），所以我们可以得出结论（要移动left和right之间最小的那个，也就是一开始说明的两种情况）。此时最大的容积为2*3=6

• 最后，对于左指针和右指针对应高度相等的情况（数组高度为[2,1,3,2]）

  如下图所示：

Java

Solution :

class Solution {
    public int maxArea(int[] height) {
        if(height ==null || height.length < 2) return 0;
        // 初始化left,right和area
        int area = 0;
        int left = 0;
        int right = height.length -1;
        // 左指针索引小于右指针时
        while(left<right){
            // 更新面积
            area = Math.max(area,(right-left)*Math.min(height[left],height[right]));
            // 移动规则
            // 左指针对应高度 > 右指针对应高度  （结果：右指针左移，这样右指针才能找到比当前大的高度）
            if(height[left] > height[right]) right --;
            // 左指针对应高度 < 右指针对应高度     (结果：左指针右移，这样左指针才能找到比当前大的高度)
            else if (height[left] < height[right]) left ++;
            // 左指针对应高度 = 右指针对应高度   （结果： 左右指针同时移动一位 即右指针左移，左指针右移）
            else{
                left++;
                right--;
            }
        }
        return area;
    }
}

打赏