题目链接

点击查看【music163】

题目描述

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

示例

示例1：

0011.jpg

输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

提示

  • n = height.length
  • 2 <= n <= 3 * 104

  • 0 <= height[i] <= 3 * 104

    思路

    双指针

    在初始时，左右指针分别指向数组的左右两端，设为i,j，他们之间的距离设为x，则它可以容纳的水量为0011-乘最多水的容器 - 图2
    双指针的正确性证明详见官方题解。
    总而言之，容纳水的高度由最短的边决定，移动长边会缩短两边之间的距离，这样只会减少容纳水的量，因此我们移动较短的一条边并期望能够得到更长的边来弥补距离缩短带来的损失，如此一来就能得到更大的容量。

    题解

    1. class Solution {
    2.  public:
    3.   int maxArea(vector<int>& height) {
    4.       int i = 0, j = height.size() - 1;
    5.       int ans = 0;
    6.       while (i < j) {
    7.           int area = min(height[i], height[j]) * (j - i);
    8.           ans = max(ans, area);
    9.           if (height[i] <= height[j]) {
    10.               i++;
    11.           } else {
    12.               j--;
    13.           }
    14.       }
    15.       return ans;
    16.   }
    17. };

    复杂度分析

  • 时间复杂度：0011-乘最多水的容器 - 图3，双指针总计最多遍历整个数组一次。

  • 空间复杂度：0011-乘最多水的容器 - 图4，只需要额外的常数级别的空间。

    题外话

    类似题目还有0042接雨水click
    不过两题还是有区别的，本题是求最大的容量，而接雨水一题是求总容量。