原题描述
+
给你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。
原题链接:https://leetcode-cn.com/problems/container-with-most-water
思路解析
+
这题不难,因为很多人都能想出时间复杂度为 暴力搜索的方法,题干也没有限制做法,所以即使作为一个中等难度题目也有高达63.3%的通过率。
这里我们介绍一个时间复杂度为 的方法,它的思路也非常简单。我们使用首尾两个指针,一边计算面积,一边让两个指针向中间移动。
假设数组为 ,首尾指针分别为 和 ,那么盛水面积的计算公式为: 下一步我们要向中间移动指针,逐步减少 和 之间的距离,那么我们应该移动哪个指针呢?我们需要摸清上面公式的数字规律,所以给出数学证明。
无论移动哪个指针, 一定减少。假设移动 和 中较大的数字对应的指针,为了不是一般性,我们就假设当前 ,此时当移动 时 ,我们一定有 进一步我们能得到 即新面积一定小于旧面积,所以每次高度较大的指针是错误的。只有移动高度较小的指针,才有可能遇到更大的面积值。
所以结论就是,每次将高度较小的指针向中间移动,并计算面积,直到两个指针相遇为止。怎么样,很简单吧~
复杂度分析
+
计算过程
+
C++参考代码
+
class Solution {
public:
int maxArea(vector<int>& height) {
int i = 0, j = height.size() - 1, res = 0;
while (i != j) {
int area = (j - i) * min(height[i], height[j]);
res = max(res, area);
if (height[i] < height[j]) ++i;
else --j;
}
return res;
}
};