HHot 100C++ 图解

11. 盛最多水的容器

中等 双指针 6 帧动画 在力扣上做

一句话套路对撞指针,每次移动较矮的一侧

题目描述

给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明:你不能倾斜容器。

 

示例 1:

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

示例 2:

输入:height = [1,1]
输出:1

 

提示:

  • n == height.length
  • 2 <= n <= 105
  • 0 <= height[i] <= 104

思路

时间O(n)
空间O(1)

思路

从最宽的两端开始。面积 = 宽 × min(高),宽度只会变小,所以想变大必须换掉「较矮的那根」——移动高的一端必然不更优。

反例

移动较高的一端,min 不会变大而宽度变小,面积必降。

图解

1 0 8 1 6 2 2 3 5 4 4 5 8 6 3 7 7 8
数组(来自本仓库测试数据,下标从 0 开始)

逐帧动画

1 / 6

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/02_two_pointers.cpp16 行
namespace lc0011 {
class Solution {
 public:
  int maxArea(vector<int>& height) {
    int l = 0, r = (int)height.size() - 1, ans = 0;
    while (l < r) {
      ans = max(ans, (r - l) * min(height[l], height[r]));
      if (height[l] < height[r])
        ++l;
      else
        --r;
    }
    return ans;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q11_container_with_most_water7 行
lc0011::Solution s;
vector<int> a{1, 8, 6, 2, 5, 4, 8, 3, 7};
CHECK_EQ(s.maxArea(a), 49);
vector<int> b{1, 1};
CHECK_EQ(s.maxArea(b), 1);
vector<int> c{4, 3, 2, 1, 4};
CHECK_EQ(s.maxArea(c), 16);

↑↓ 选择↵ 打开/ 随时唤起