盛最多水的容器

发表于 | 分类于 | 阅读次数：
本文字数： 895 | 阅读时长 ≈ 2 分钟

问题提出

#11 盛最多水的容器

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

解题思路

若采用暴力法求解，时间复杂度为O(n2)，不够优雅，本题有一种时间复杂度为O(n)的算法。

要想围住的面积最大，需要尽量保证

  • 底边长比较大（两数在数组中的距离较远）
  • 两数的最小值比较大

为了达到这两个目标，我们从底边长较大开始，定义两个变量 i，j 来记录两数的位置，并将其初始值置为 0 和 size-1。虽然此时底边长度最大，但由于这两条边可能都比较短，此时的面积很可能不是最大面积。现在的任务便是如何缩小底边的同时尽量获得最大的边长。

不妨设此时两边边长不等，倘若将长的那一边移进，显然新的面积恒小于当前面积（因为限制当前面积的不是这条长的边，新的面积的底边长缩小，竖直边长不大于原边长）；因此要想获得更大的面积，只能移进那条较短的边。

按照这个思路，不断移进短的边，直到 i 和 j 相等，在移进的过程中记录最大边长即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
#define MIN(x, y) ((x) < (y) ? (x) : (y))

int maxArea(vector<int>& height) {
    int i = 0, j = height.size() - 1;
    int area = 0;
    while (i < j) {
        int temp = (j - i) * MIN(height[i], height[j]);
        if (temp > area) area = temp;
        if (height[i] > height[j]) j--;
        else i++;
    }
    return area;
}