LeetCode百题【盛最多水的容器】

题目描述

解法

双指针+贪心
- 通过题目描述，需要获得最大的面积，很容易想到双指针，通过左右指针进行变换，改变面积
- 指针如何移动：为了获得最大的面积 ->即长*宽，让这两个相乘的因子最大（贪心思想）
  - 长：就是左右指针的距离，一开始分别在左右两端—-长度最大
  - 宽：就是垂线的高度，由于盛水的短板效应，这里应该选择两者短的那个。
    
    所以我们应该移动短的那个指针，让高度的落差减小。
- 最后题目要求是要求最大面积，每次移动后还需要对面积进行比较，更新最大面积

代码

class Solution {
    public int maxArea(int[] height) {
        int area=0;
        int left=0,right=height.length-1;
        
        while (left<right){
            //当左右指针相遇，遍历结束
            area=Math.max(area,Math.min(height[left],height[right])*(right-left));
            //更新最大面积
            //Math.min(height[left],height[right]) 求“短板”
            //(right-left) 矩形的长
            //当前面积=短板（高）*长->Math.min(height[left],height[right])*(right-left)
            if(height[left]<height[right]){
                left++;
            }
            else {
                right--;
            }
            //改变高度的落差
        }
        return area;
    }
}