Leetcode 11

题目描述

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

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

• 示例：

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

提交答案

class Solution {
    public int maxArea(int[] height) {
        final int length = height.length;
        int first = 0;
        int last = length - 1;
        int maxArea = Math.min(height[first], height[last]) * (last - first);

        for (int i = 0; i < length; i++) {
            if (first == last) {
                break;
            } else if (height[first] <= height[last]) {
                first++;
            } else if (height[first] > height[last]) {
                last--;
            }

            maxArea = Math.max(maxArea, Math.min(height[first], height[last]) * (last - first));
        }
        return maxArea;
    }
}

执行用时: 5 ms , 在所有 Java 提交中击败了 45.35% 的用户

内存消耗: 40.1 MB , 在所有 Java 提交中击败了 21.43% 的用户

题解反思

这道题采用 “双指针” 的思路。用 first 和 last 分别代表长方形的两边，初始值分别为 0 和 length-1。

• 分别用一个指针标识整个长方形的两边，这两个指针所对应的数组索引之差就是长方形的底边，这时整个长方形的面积为：Math.min(height[first], height[last]) * (last - first)，并用 maxArea 记录最大的面积。
• 将整个长方形逐渐向中间趋近，以防止漏掉中间有较大的长边。这时我们分别比较 height[first] 和 height[last] 的值，也即这个长方形左右两边的高，若左边较低，就将左指针右移（first++），若右边较低，就将右指针左移（last--）。
• 左右指针移动之后，便再次计算当前长方形的面积(Math.min(height[first], height[last]) * (last - first))。
• 并将该面积和 MaxArea 中保存的值作对比，以将当前较大的面积保存在 MaxArea 变量中。
• 当左指针和右指针相遇时，即 first == last，就终止数组的循环，此时 MaxArea 中保存的即为最大面积。

复杂度分析

• 时间复杂度：O(n)，双指针最多遍历整个数组一次。
• 空间复杂度：O(1)，无需额外的空间开销，只需存储左右指针和最大面积的值即可。

优化

虽然按照自己的题解是能够通过所有的测试用例的，但是看了评论区的一些解答，发现在代码的可读性上还是可以优化的。

在循环时，自己采用的是 for (int i = 0; i < length; i++) 而将循环中断的条件放在了循环体中，即：if (first == last) { break; }。

想一下，如果将循环中断的条件放在循环的声明中，并采用 while 循环，整个代码看起来就会更加可读一些，如下：

public int maxArea(int[] height) {
        final int length = height.length;
        int first = 0;
        int last = length - 1;
        int maxArea = Math.min(height[first], height[last]) * (last - first);
        
        while(first < last){
            if (height[first] <= height[last]) {
                first++;
            } else if (height[first] > height[last]) {
                last--;
            }
            maxArea = Math.max(maxArea, Math.min(height[first], height[last]) * (last - first));
        }
        return maxArea;
}

这样就会比之前采用 for i 循环看起来更优雅也更易读一些，且更清楚的表达了自己的解题逻辑。

本文首发于「愚一笔记」。