力扣【LeetCode】—— 11. 盛最多水的容器【java】

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了力扣【LeetCode】—— 11. 盛最多水的容器【java】，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2486字，纯文字阅读大概需要4分钟。

内容图文

题目地址：https://leetcode-cn.com/problems/container-with-most-water/

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

解法一（暴力求解）：
?思路：遍历计算最大值，两层循环，选中一条垂直线，然后根据这条线依次遍历后面的，根据最短的线计算面积，获取最大值即可

public class ContainerWithMostWater {
    // 暴力求解
    public static int maxArea(int[] height) {
        int area = 0;
        for (int i = 0; i < height.length; i++) {
            // j 从 i位置后面一个开始
            for (int j = i + 1; j <height.length; j++) {
            	// Math.min(height[i],height[j]) * (j-i) 计算面积
            	// 和原来计算结果比较大小 ，择大即可
                area = Math.max(area,Math.min(height[i],height[j]) * (j-i));
            }
        }
        return area;
    }
    public static void main(String[] args) {
        int[] arr = new int[]{4,3,2,1,4};
        System.out.println(maxArea(arr));
    }
}

解法二（双指针移动）— 参考官网：
?思路：首先用第一根和最后一根做比较，可以计算出矮的那根对应的最大面积（装水只能装到矮的那个的高度），同时可以在后面的计算中排除矮的这根，这样依次按照同样的方式从两边向中间靠拢，并计算面积，找到最大值即可。
?示例图（来源：leetcode官网）

写法一（参考官网）：

/**
 * 参考官方解法（双指针）
 */
public int maxArea3(int[] height) {
    int area = 0;
    int i = 0,j = height.length-1;
    while (i < j) {
        int minH = Math.min(height[i],height[j]);
        area = Math.max(area,minH * (j-i));
        if (height[i] < height[j]) {
            i ++;
        }else {
            j --;
        }
    }
    return area;
}

另一种写法

到网站翻到一种牛掰写法（原理和上一种解法一致）

/**
 * 到国外网站翻到了一种牛掰写法（原理和上一种解法一致）
 */   
public int maxArea(int[] height) {
    int area = 0;
    for (int i = 0,j = height.length-1; i<j;) {
        int minH = height[i] < height[j] ? height[i++] : height[j--];
        //j-i加1的原因是上面i++/j--的时候向右或向左移动了一格，方便下次遍历
        //所以在进行当前计算的时候要还原到原来横坐标的宽度
        area = Math.max(area, minH * (j - i +1));
    }
    return area;
}

上一种写法进行简单的优化

// 再优化，将j-i的操作提到 i++ j-- 操作的前面
public int maxArea(int[] height) {
    int area = 0;
    for (int i = 0,j = height.length-1; i<j;)
        area = Math.max((j-i)* (height[i] < height[j]?height[i++]:height[j--]),area);
    return area;
}

参考如上写法，对第二种解法简单进行简单改造
后面几种的写法思路、本质都是一样，只是写法有些不同而已

public static int maxArea4(int[] height) {
    int area = 0;
    int i = 0,j = height.length-1;
    while (i < j) {
        int minH = height[i] < height[j] ? height[i++] : height[j--];
        area = Math.max(area,minH*(j-i+1));
    }
    return area;
}

内容总结

以上是互联网集市为您收集整理的力扣【LeetCode】—— 11. 盛最多水的容器【java】全部内容，希望文章能够帮你解决力扣【LeetCode】—— 11. 盛最多水的容器【java】所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端