leetcode：11. 盛最多水的容器

题目

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。

示例 1：
image.png

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

示例 2：

  1. 输入：height = [1,1]
  2. 输出：1

解答 & 代码

双指针（left、right）

容器可容纳水的高度是由容器左、右两边界中的短板决定的。
因此，容器的容量 cur_cap = min(height[left], height[right]) * (right - left)

在每个状态下：

  • 计算当前左、右边界构成的容器的容量 cur_cap
  • 更新全局最大容量 max_cap
  • 双指针移动：将高度较低的那个边界往里收缩一格

解释：为什么将短板一侧往里收缩一格？

  • 容器的容量 = 宽 * 高（取决于两侧短板的高）

  • 无论是长板还是短板往里收缩一格，宽都为减少，那么想要得到更大的容量，就只能希望高增加。而容器的高取决于两侧的短板，那么，

    • 如果将长板一侧往里移动一格，容器的高（短板）要么不变，要么变小，不可能变大，因此容量只会更小；
    • 而如果将短板一侧往里移动一个，容器的高（短板）是有可能变大的，那么容量就有可能变大
      1. class Solution {
      2. public:
      3. int maxArea(vector<int>& height) {
      4.    int max_cap = 0;                                // 最大容量
      5.    int left = 0;                                        // 左边界下标
      6.    int right = height.size() - 1;    // 右边界下标
      7.    while(left < right)
      8.    {
      9.          // 当前两个边界构成的容器的容量，即 [left right] 之间的矩形面积
      10.        int cur_cap = min(height[left], height[right]) * (right - left);
      11.          // 更新最大容量
      12.        max_cap = max(max_cap, cur_cap);
      13.        // 双指针移动：移动高度较低的一边，往里收缩一格
      14.        if(height[right] < height[left])
      15.            --right;
      16.        else
      17.            ++left;
      18.    }
      19.    return max_cap;
      20. }
      21. };
      复杂度分析：设数组长度 N

  • 时间复杂度 O(N)

  • 空间复杂度 O(1)

执行结果：

  1. 执行结果：通过
  3. 执行用时：88 ms, 在所有 C++ 提交中击败了 17.10% 的用户
  4. 内存消耗：57.5 MB, 在所有 C++ 提交中击败了 76.92% 的用户