问题描述

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

说明：你不能倾斜容器。

解题2方法

/**
 * 11. 盛最多水的容器
 * https://leetcode-cn.com/problems/container-with-most-water/
 * @author 爱吃鱼的乌贼
 *
 */
public class Leetcode11 {
    /**
     * 用双指针的方法，让两个指针分别指向第一个和最后一个值，因为能够剩多少水，靠的是较小的挡板，所以
     * 哪一个指针对应的小，就移动哪一个，毕竟移动较大的指针是没有意义的，因为两个指针的距离是变小的，容量又是
     * 小的挡板*距离，所以移动高的挡板，没有意义，不可能大于不移动的容量
     * @param height
     * @return
     */
    public int maxArea(int[] height) {
        int len = height.length;
        //开始下标
        int first = 0;
        //结束下标
        int last = len-1;
        //最大容量
        int max = 0;
        //如果开始下标小于结束下标，则进行移动判定
        while(first<last) {
            //1、获取下标之间的距离
            int t = last-first;
            //2、获取叫矮的挡板值
            int first_value = height[first];
            int last_value = height[last];
            int min = getMin(first_value, last_value);
            //3、获取当前的容量
            int h = t*min;
            if(h>max) {
                max=h;
            }
            //4、移动较小的下标
            if(first_value<last_value) {
                first++;
            }else {
                last--;
            }
        }
        return max;
    }
    public int getMin(int first,int second) {
        if(first>=second) {
            return second;
        }else {
            return first;
        }
    }
    public static void main(String[] args) {
        int[] height = new int[] {1,8,6,2,5,4,8,3,7};
        System.out.println(new Leetcode11().maxArea(height));
    }
}

总结

我一开始还以为用动态规划法，后面发现没有用，最后的选择还是需要把前面的都算一遍，所以怎么想都想不到解决办法，最后看了题解才发现有一种解法叫做：双指针法。

果然如果不看题解，靠自己想，怎么都想不到的，只有看了题解才会知道！

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