LeetCode-盛最多水的容器

LeetCode-盛最多水的容器

题目:#11 盛最多水的容器

链接:https://leetcode-cn.com/problems/container-with-most-water/
难度:中等

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

说明: 你不能倾斜容器,且n的值至少为2
leetcode-container-with-most-water-1

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

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


方法一:暴力法

直接遍历枚举出所有结果取最大值,太简单就略过了

代码

private static int maxArea(int[] height) {
    int ans = 0;
    for (int i = 0; i < height.length - 1; i++) {
        for (int j = i + 1; j < height.length; j++) {
            ans = Math.max(ans, (j - i) * Math.min(height[j], height[i]));
        }
    }
    return ans;
}

复杂度分析:

方法二:双指针法

这题中等难度主要就在于理解双指针法

代码

public int maxArea(int[] height) {
    int i = 0, j = height.length - 1, ans = 0;
    while (i != j) {
        ans = Math.max(ans, (j - i) * Math.min(height[i], height[j]));
        if(height[i]<=height[j]) i++;
        else j--;
    }
    return ans;
}

复杂度分析