LeetCode：11. Container With Most Water（求能装多少水问题）-蒲公英云

LeetCode：11. Container With Most Water（求能装多少水问题）

野性酷女 2022-04-04 07:50 219阅读 0赞

文章最前：我是Octopus，这个名字来源于我的中文名—章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人github ；这博客是记录我学习的点点滴滴，如果您对 Python、Java、AI、算法有兴趣，可以关注我的动态，一起学习，共同进步。

相关文章：

LeetCode：55. Jump Game（跳远比赛）
Leetcode：300. Longest Increasing Subsequence（最大增长序列）
LeetCode：560. Subarray Sum Equals K（找出数组中连续子串和等于k

文章目录：

题目描述：

java实现方法1：(暴力算法)brute force

python实现方式1：

java实现方法2：（双指针的方式）

python实现方式2：

github地址：https://github.com/zhangyu345293721/leetcode

题目描述：

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

说明：你不能倾斜容器，且 n 的值至少为 2。

format_png

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

实例:

输入: [1,8,6,2,5,4,8,3,7]
输出: 49

java实现方法1：

/**
     * 暴力算法（brute force）
     *
     * @param height 长度数组
     * @return 面积
     */
    private int maxArea(int[] height) {
        if (height == null || height.length < 2) {
            return 0;
        }
        int maxArea = 0;
        for (int i = 0; i < height.length - 1; i++) {
            for (int j = i + 1; j < height.length; j++) {
                int high = Math.min(height[i], height[j]);
                maxArea = Math.max(maxArea, high * (j - i));
            }
        }
        return maxArea;
    }

时间复杂度：O（n^2）

空间复杂度：O(1)

python实现方式1：

def max_area(heights: List[int]) -> int:
    '''
        求最大面积
    Args:
        heights:长度数组
    Returns:
        最大面积
    '''
    if len(heights) < 2:
        return 0
    max_area = 0
    for i in range(len(heights) - 1):
        for j in range(i, len(heights)):
            high = min(heights[i], heights[j])
            wide = abs(i - j)
            area = high * wide
            if area > max_area:
                max_area = area
    return max_area

时间复杂度：O（n^2）

空间复杂度：O(1)

java实现方法2：（双指针的方式）

/**
     * 快速排序的基本思想
     *
     * @param height 长度数组
     * @return 面积
     */
    private static int maxArea2(int[] height) {
        int maxArea = 0;
        int i = 0;
        int j = height.length - 1;
        while (i < j) {
            int area = Math.min(height[i], height[j]) * (j - i);
            maxArea = Math.max(maxArea, area);
            if (height[i] < height[j]) {
                i++;
            } else {
                j--;
            }
        }
        return maxArea;
    }

时间复杂度:O(n)

空间复杂度:O(1)

python实现方式2：

def max_area2(heights: List[int]) -> int:
    '''
        求最大面积
    Args:
        heights:长度数组
    Returns:
        最大面积
    '''
    if len(heights) < 2:
        return 0
    max_area, i, j = 0, 0, len(heights) - 1
    while i < j:
        area = min(heights[i], heights[j]) * abs(i - j)
        max_area = max(area, max_area)
        if heights[i] < heights[j]:
            i += 1
        else:
            j -= 1
    return max_area