LeetCode Hot 100：11. 盛最多水的容器

题目

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

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

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

说明：‌你不能倾斜容器。

示例 1：‌

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

示例 2：‌

输入：‌height = $1,1$
输出：‌1

提示：‌

n == height.length
2 <= n <= 10^5
0 <= height[i] <= 10^4

题解

Go：

func maxArea(height []int) int {
    left, right, maxArea := 0, len(height) - 1, 0
    for left < right {
        area := (right - left) * min(height[left], height[right])
        if height[left] < height[right] {
            left ++
        } else {
            right --
        }
        if area > maxArea {
            maxArea = area
        }
    }
    return maxArea
}

Go 介意且完全不允许在相同的作用域中有变量和函数重名。然而在maxArea()函数里新建名为maxArea的变量就没问题。

本质上是两个指针向中间逼近，只是指向更矮木板的那个指针移动优先级更高。

Java：

照搬逻辑的话是下面这样：

Java

class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1, maxArea = 0, currHeight;
        while (left < right) {
            if (height[left] > height[right]) {
                currHeight = height[right];
            } else {
                currHeight = height[left];
            }
            int area = (right - left) * currHeight;
            if (height[left] < height[right]) {
                left ++;
            } else {
                right --;
            }
            if (area > maxArea) maxArea = area;
        }
        return maxArea;
    }
}

还可以凹，不是每次迭代都需要计算height，我们可以：

Java

class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1, maxArea = 0, currHeight;
        while (left < right) {
            currHeight = Math.min(height[left], height[right]);
            maxArea = Math.max(maxArea, (right - left) * currHeight);

            while (left < right && height[left] <= currHeight) left ++;
            while (left < right && height[right] <= currHeight) right --;
        }
        return maxArea;
    }
}

这个方案可以避免无谓的性能损耗。

然而我发现我的 Java 答案仅仅击败了99.02%的选手‌。于是好奇那些耗时 0ms 的选手都是怎么写的。

如下：

Java

class Solution {
    private static int[] res = new int[]{49,1,16,2,1,1,0,0,4,9,7,3,9,8,49,36,17,42,24,24,200,62,25,1000,25,96,55,
    84,70,112,72,80,36,55,42,18048,14608,15423,17472,17848,16560,15252,15936,17557,17108,92344,95933,94080,94187,
    468905,4913370,48431514,48762645,48267879,49024602,97658256,50000000,402471897,705634720,721777500,887155335,
    995042464,999990000,3655,20};
    private static int cnt = 0;
    public int maxArea(int[] height){
        return res[cnt++];}
}

我突然释怀地笑😃

记录

Java 中的min()和max()是包含在 Math 包内的。使用时需注意。
没了