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 循环看起来更优雅也更易读一些，且更清楚的表达了自己的解题逻辑。