---

前言

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

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

一、解题思路

先假设无重复值,左右两个指针左边跟右边比大小,谁小结算谁的水量
两个左右两个指针依次划的过程中算出所有水量的最大值就是答案

它不是严格要求每一个数都能够准确的算出来它的答案
它只关心有没有推高答案的可能性
为啥你不知道这道题怎么做?但是你看数据量,你就知道自己一定会整出一个O(N)的解,那势必可能会想到双指针,谁大移动谁跟谁小移动谁都试一遍这题就出来了,不用知道为什么有可能都能猜出来

如图,移动小的指针,每次计算水量,不会错过答案

只关注它推高答案的可能性,但是我们不去严格纠结每一个位置的值,它具体答案是多少

代码

class Solution {
    public int maxArea(int[] height) {
        int l=0;
        int r=height.length-1;
        int max=0;
        while(l<r){
            max=Math.max(max,Math.min(height[l],height[r])*(r-l));
            if(height[l]>height[r]){
                r--;
            }else{
                l++;
            }
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

总结

遇到数组问题,并且题目的数据量要求使用O(n)的解,我们可以考虑使用双指针
我们可以比较两个指针的数,想想怎么移动指针
在这题中,我们发现谁小移动谁就可以得出答案