LeetCode 11: 盛最多水的容器

这是一道标准的双指针应用题，基本上看到题目第一时间就会想到用双指针来解。本文将详细讨论如何解决LeetCode上的一道热门问题——盛最多水的容器，同时展示如何通过双指针技巧解决此问题。

image-20240410111231283

问题描述

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

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

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

说明：你不能倾斜容器。

示例

输入: [1,8,6,2,5,4,8,3,7] 输出: 49

思路分析

解决这个问题的关键是理解短板效应，并且有效更新最大水量。这里，我们采用双指针法：

  • 左指针（fast）：限定左边边界，当为短板时向后移动。
  • 右指针（slow）：限定右边边界，当为短板时向前移动。

通过这种方式，我们能够在一次遍历中解决问题，同时保持代码的简洁性和效率。

代码实现

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

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组长度。我们只需要遍历一次数组。
  • 空间复杂度：O(1)。我们只使用了常数级别的额外空间。

结论

这种左右双指针几乎是最基础的双指针题目，个人觉得这题只有easy难度。