当前位置：首页 > article >正文

【每日一题】LeetCode - 盛最多水的容器

article 2024/10/27 6:07:54

给定一个长度为 n 的整数数组 height。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])。要求找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

输入示例：

height = [1,8,6,2,5,4,8,3,7]

输出：

解释：
在此情况下，最大水容量为 49，选择的两个端点分别在位置 1 和位置 8。

解题思路

这个问题的关键在于找到一对垂线，使得它们之间的距离乘以两条线中较短的一条的高度值达到最大。我们可以使用以下两种算法进行求解。

暴力法

最直接的方法是遍历每一对垂线，计算其形成的容器容量，取其中的最大值。这种方法的时间复杂度较高，但能保证得到正确的结果。

代码实现：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int l = 0, ans = 0;
        for(int i = 0; i < height.size(); i++) {
            for(int k = i; k < height.size(); k++) {
                int m = min(height[i], height[k]);
                ans = max((k - i) * m, ans);
            }
        } 
        return ans;
    }
};

时间复杂度分析：

暴力法的时间复杂度为 $O(n^2)$ ，因为我们需要遍历数组中的每一对垂线。空间复杂度为 $O (1)$ ，仅使用了常量空间。

优缺点：

暴力法虽然简单直接，但在数据量较大时效率低下。适合数据量较小的情况。

在这里插入图片描述

双指针法

双指针法是一种优化算法，它使用左右两个指针从数组两端逐渐向中间移动。在每一步中，通过计算两个指针指向的垂线形成的容器面积，并与当前最大面积进行比较，保留较大的值。然后将较短的垂线的指针向中间移动，这样可以有效减少计算量。

我们使用两个指针从数组两端向中间逼近来寻找最大容积。由于面积由最短的边和两边之间的距离决定，因此我们可以使用以下策略来不断逼近最大面积：

初始化左指针 l 指向数组的最左端，右指针 r 指向数组的最右端。
计算以 l 和 r 两条线组成的容器的面积 Area = (r - l) * min(height[l], height[r])。
若当前面积比已有的最大面积大，则更新最大面积。
比较 height[l] 和 height[r] 的高度：
- 若 height[l] < height[r]，说明左边的线较短，为了可能找到更大的面积，我们将左指针右移一格 l++。
- 否则，右指针左移一格 r--。
重复上述过程，直到左右指针相遇为止。

为什么这种方法有效？

因为若一对指针组成的容器容量较小，由于容量取决于 较短的边，所以只移动较短的那条边，可能才有机会得到更大的容积。而移动较长的那边对容积并没有帮助。

代码实现：

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

代码解析

l 和 r 初始化为左右两端的指针。
ans 用于存储最大面积，初始为 0。
while(l < r)：当左右指针相遇时停止迭代。
每次迭代中更新 ans 为当前最大面积。
比较 height[l] 和 height[r]，移动较短的一端的指针，直到 l >= r。

时间复杂度分析：

双指针法的时间复杂度为 $O (n)$ ，只需遍历一遍数组。空间复杂度为 $O (1)$ 。

优缺点：

双指针法效率更高，适用于大数据量的情况，能在不遍历所有组合的前提下找到最优解。

在这里插入图片描述

两种方法对比

方法	时间复杂度	空间复杂度	优势	劣势
暴力法	$O(n^2)$	$O (1)$	实现简单，便于理解	数据量大时效率低下
双指针法	$O (n)$	$O (1)$	效率高，适用于大数据量	实现稍微复杂