Leetcode 每日一题 11. 盛最多水的容器

目录

引言

问题背景

输入输出规范

示例解析

示例 1

示例 2

算法策略

Java代码实现

复杂度分析

结语

引言

在算法的世界里，有些问题虽然简单，但却是锻炼算法思维的绝佳练习。今天，我们将深入探讨一个在面试中经常出现的问题——“接雨水”问题。这个问题不仅考验我们对数组操作的熟练程度，还考察我们如何利用数组的特性来优化算法。本文将详细介绍如何使用双指针法解决“接雨水”问题，并提供Java语言的实现。

问题背景

给定一个长度为 n 的整数数组 height，代表 n 条垂线的高度。我们的任务是找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。这个问题实际上是在询问，如何通过选择两条垂线来最大化容器的储水量。

输入输出规范

• 输入：整数数组 height，一个包含垂线高度的数组。
• 输出：整数 maxArea，表示容器可以储存的最大水量。

示例解析

示例 1

• 输入：height = [1,8,6,2,5,4,8,3,7]
• 输出：49
• 解释：选择高度为 8 和 6 的两条线，它们与 x 轴构成的容器能够容纳的最大水量为 49。

示例 2

• 输入：height = [1,1]
• 输出：1
• 解释：选择两条高度为 1 的线，它们与 x 轴构成的容器能够容纳的最大水量为 1。

算法策略

双指针法是解决此类问题的常用策略。我们利用数组的特性，通过两个指针 left 和 right 分别指向数组的两端，通过调整这两个指针的位置来寻找能够构成最大储水量的两条线。

• 初始化：left 指向数组的开始，right 指向数组的末尾。
• 计算面积：计算两条线之间的宽度与它们高度的最小值的乘积作为当前面积。
• 调整指针：
  • 如果左边的高度小于右边的高度，则 left 向右移动，因为我们需要一个更高的线来增加储水量。
  • 如果左边的高度大于或等于右边的高度，则 right 向左移动，因为我们需要一个更高的线来增加储水量。
• 循环直至相遇：重复上述步骤，直到 left 和 right 相遇。

Java代码实现

java

public class Solution {
    public int maxArea(int[] height) {
        int max = 0;
        int left = 0, right = height.length - 1; // 初始化左右指针
        while (left < right) { // 循环直至左右指针相遇
            int currentArea = (right - left) * Math.min(height[left], height[right]);
            if (max < currentArea) {
                max = currentArea; // 更新最大面积
            }
            if (height[left] < height[right]) {
                left++; // 增加左边的高度
            } else {
                right--; // 增加右边的高度
            }
        }
        return max; // 返回最大面积
    }
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 height 的长度。每个元素最多被访问两次。
• 空间复杂度：O(1)，只需要常量级的额外空间来存储结果。

通过图片

leetcode地址

11. 盛最多水的容器 - 力扣（LeetCode）

结语

通过双指针法，我们不仅解决了“接雨水”问题，还展示了如何利用数组的特性来优化算法。这种方法的时间复杂度和空间复杂度都非常低，适用于处理大规模数据集。希望这篇文章能够帮助你深入理解双指针法，并将其应用到实际问题中。如果你有任何疑问或想要进一步探讨，欢迎在评论区交流。同时，如果你觉得这篇文章对你有帮助，不妨点个赞或者分享给需要的朋友。让我们一起进步，一起成长！