dsfds' blog

学海无涯，回头是岸

0%

LeetCode | 11 盛最多水的容器

发表于 更新于 分类于 Valine：

题目

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

注意：不能倾斜容器，n 至少是 2。

题解

如果使用暴力算法，那么时间复杂度为 $O(n^2)$。如果使用双指针法，那么时间复杂度降为 $O(n)$。如下所示。

  1. 初始化两个指针 first 和 last 分别指向数组头和尾；
  2. 当 last 指向的值较小时，计算一个面积，并决定是否保留，然后 last-- ；
  3. 当 first 指向的值较小时，计算一个面积，并决定是否保留，然后 first++；
  4. 从第 2 步重新执行，直到 first == last，返回最大值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int maxArea(int *height, int heightSize)
{
    int res = 0, aux = 0;
    int first = 0, last = heightSize - 1;
    while (first < last) {
        if (height[first] < height[last]) {
            aux = height[first] * (last - first);
            res = aux > res ? aux : res;
            first++;
        } else {
            aux = height[last] * (last - first);
            res = aux > res ? aux : res;
            last--;
        }
    }
    return res;
}

我们还可以对上面的算法进行一些改进。在上面的算法中，我们每次将指针挪动一个位置（向左或向右），然后计算面积并进行比较。这个面积的计算是否每次都有必要呢？其实并不必要，每次挪动指针后，所求区域的长度都会减小，只有区域的宽度增加我们才有重新计算面积的必要，即指针新指向的值大于它原来指向的值，我们才需要再次计算面积。基于此，我们可以对算法进行改进，如下所示。

LeetCodeSolution11.cview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int maxArea(int *height, int heightSize)
{
    int res = 0, aux = 0;
    int first = 0, last = heightSize - 1;
    while (first < last) {
        aux = (last - first) * 
            (height[first] < height[last] ? height[first] : height[last]);
        res = aux > res ? aux : res;
        if (height[first] < height[last])
            while (++first < max && height[min] <= height[min-1])
                // 新指针指向的值不大于原来的值 继续减小指针即可
                continue;
        else
            while (--last > first && height[last] <= height[last+1])
                // 新指针指向的值不大于原来的值 继续减小指针即可
                continue;
    }
    return res;
}