当前位置:首页 > 大杂烩 > 正文内容

算法解析:盛最多水的容器 —— 双指针法的高效应用

高老师1周前 (09-25)大杂烩23

算法解析:盛最多水的容器——双指针法的高效应用

在数组相关的算法题中,“盛最多水的容器”是一道经典题目,核心考察对“优化时间复杂度”的理解。题目看似需要暴力遍历所有可能的容器组合,但通过“双指针法”可将时间复杂度从 O(n²) 降至 O(n),大幅提升效率。本文将从题目分析入手,详解双指针法的原理、代码实现及边界情况处理,帮助彻底掌握这一解题思路。

一、题目理解:容器的水量如何计算?

首先需明确题目中的“容器”定义与水量计算逻辑,避免理解偏差:

  • 容器构成:由数组中两条不同的垂线(第 i 条垂线高度为 height[i],底部在 x 轴上)和 x 轴共同围成,形状为“矩形”(或“直角梯形”,但水量由最短边决定,本质按矩形计算);
  • 水量计算:容器的容量 = 底边长 × 高度,其中:
    • 底边长:两条垂线在 x 轴上的距离(即两个索引的差值 j - i,假设 j > i);
    • 高度:两条垂线中较短的那条的高度(因为水无法超过较短边,否则会溢出,即 min(height[i], height[j]));
  • 目标:在所有可能的两条垂线组合中,找到容量最大的组合,返回最大容量值。

示例验证

以题目中的示例 1 为例:

  • 输入数组:[1,8,6,2,5,4,8,3,7]
  • 最优组合:索引 1(高度 8)和索引 8(高度 7)
  • 计算过程:底边长 = 8 - 1 = 7,高度 = min(8,7) = 7,容量 = 7×7 = 49,与示例输出一致。

二、解题思路:从暴力到双指针的优化

1. 暴力解法(不推荐)

最直观的思路是“遍历所有可能的两条垂线组合”,计算每个组合的容量并记录最大值。但这种方法的时间复杂度为 O(n²)(n 为数组长度),当 n 较大(如 n=10⁴)时,会因计算量过大导致超时。

暴力解法代码(仅作对比)

class Solution {
    function maxArea($height) {
        $n = count($height);
        $maxCapacity = 0;
        // 遍历所有 i < j 的组合
        for ($i = 0; $i < $n; $i++) {
            for ($j = $i + 1; $j < $n; $j++) {
                // 计算当前组合的容量
                $width = $j - $i;
                $currentHeight = min($height[$i], $height[$j]);
                $capacity = $width * $currentHeight;
                // 更新最大容量
                $maxCapacity = max($maxCapacity, $capacity);
            }
        }
        return $maxCapacity;
    }
}

2. 双指针法(推荐,O(n) 时间复杂度)

双指针法的核心是“通过贪心策略,每次排除不可能成为最优解的组合,逐步缩小搜索范围”。具体思路如下:

  1. 初始化指针:左指针 l 指向数组起始(索引 0),右指针 r 指向数组末尾(索引 n-1);
  2. 计算当前容量:以 lr 为边界,计算当前容器的容量,更新最大容量值;
  3. 移动指针的关键逻辑
    • height[l] < height[r]:此时容器的高度由 height[l] 决定(较短边)。若向右移动右指针 r,底边长会减小,而高度最多仍为 height[l](甚至更小),容量必然减小——因此,左指针 l 向右移动(尝试寻找更长的左边,可能提升容量);
    • height[l] >= height[r]:同理,容器高度由 height[r] 决定,向左移动左指针 l 会导致容量减小——因此,右指针 r 向左移动
  4. 终止条件:当左指针 l 与右指针 r 相遇(l >= r)时,遍历结束,此时记录的最大容量即为答案。

双指针法的正确性证明

为什么这种“移动较短边指针”的策略能找到最优解?

  • 假设当前左指针 l 对应的高度 < 右指针 r 对应的高度,此时以 l 为左边的所有组合中,**lr 的组合是容量最大的**(因为其他右指针 j < r 会导致底边长更小,高度不会超过 height[l]);
  • 因此,以 l 为左边的所有组合无需再考虑,直接移动 l 即可——通过这种方式,每次移动指针都排除了一组“不可能是最优解”的组合,最终只需遍历一次数组,时间复杂度降至 O(n)。

三、完整代码实现(PHP)

结合双指针法的思路,实现代码如下,代码简洁且注释清晰,覆盖所有核心逻辑:

class Solution {
    /**
     * @param Integer[] $height 存储各垂线高度的数组
     * @return Integer 最大容器容量
     */
    function maxArea($height) {
        $n = count($height);
        if ($n < 2) {
            return 0; // 边界情况:至少需要两条垂线才能构成容器
        }
        
        $left = 0;          // 左指针:初始指向数组开头
        $right = $n - 1;    // 右指针:初始指向数组结尾
        $maxCapacity = 0;   // 记录最大容量,初始为 0
        
        // 循环:左指针 < 右指针时,持续搜索
        while ($left < $right) {
            // 1. 计算当前指针组合的容量
            $width = $right - $left;                          // 底边长 = 右指针索引 - 左指针索引
            $currentMinHeight = min($height[$left], $height[$right]); // 高度 = 较短边的高度
            $currentCapacity = $width * $currentMinHeight;    // 当前容量 = 底边长 × 高度
            
            // 2. 更新最大容量(若当前容量更大,则覆盖)
            if ($currentCapacity > $maxCapacity) {
                $maxCapacity = $currentCapacity;
            }
            
            // 3. 移动指针:始终移动较短边的指针,排除无效组合
            if ($height[$left] < $height[$right]) {
                $left++;  // 左边更短,左指针右移,寻找更长的左边
            } else {
                $right--; // 右边更短(或相等),右指针左移,寻找更长的右边
            }
        }
        
        return $maxCapacity; // 返回最终的最大容量
    }
}

四、边界情况与测试验证

1. 常见边界情况

  • 数组长度为 2:如示例 2 输入 [1,1],此时只有一种组合,容量 = 1×(1-0) = 1,代码返回正确;
  • 数组元素单调递增/递减:如输入 [1,2,3,4,5],最优组合为索引 0(1)和 4(5),容量 = 4×1 = 4;输入 [5,4,3,2,1],最优组合同样为索引 0(5)和 4(1),容量 = 4×1 = 4;
  • 数组中有相等的元素:如输入 [2,3,4,5,5,4,3,2],最优组合为索引 0(2)和 7(2),容量 = 7×2 = 14,代码会正确处理(指针移动时,相等情况下移动任意一边均可,不影响最终结果)。

2. 测试用例运行

测试用例 1

  • 输入:[1,8,6,2,5,4,8,3,7]
  • 运行过程:
    • 初始 left=0(1)、right=8(7),容量 = 8×1 = 8 → 最大容量=8;
    • 左边更短,left=1(8),此时容量 = 7×7 = 49 → 最大容量=49;
    • 右边更短(7 < 8),right=7(3),容量 = 6×3 = 18 → 不更新;
    • 右边更短(3 < 8),right=6(8),容量 = 5×8 = 40 → 不更新;
    • 两边相等(8=8),right=5(4),容量 = 4×4 = 16 → 不更新;
    • 后续继续移动指针,容量均小于 49,最终返回 49。

测试用例 2

  • 输入:[1,1]
  • 运行过程:
    • left=0right=1,容量 = 1×1 = 1 → 最大容量=1;
    • 两边相等,right=0,循环终止,返回 1。

五、总结

“盛最多水的容器”问题的核心是双指针法的贪心应用:通过“移动较短边指针”排除无效组合,在 O(n) 时间内找到最优解。解题时需注意:

  1. 明确容量计算逻辑(底边长 × 较短边高度);
  2. 理解指针移动的本质(排除不可能成为最优解的组合);
  3. 处理边界情况(数组长度 < 2 时返回 0)。

这种“通过贪心策略缩小搜索范围”的思路,也适用于其他数组优化问题(如“三数之和”“接雨水”等),掌握后可举一反三,提升算法解题效率。

扫描二维码推送至手机访问。

版权声明:本文由高久峰个人博客发布,如需转载请注明出处。

本文链接:https://blog.20230611.cn/post/908.html

分享给朋友:

“算法解析:盛最多水的容器 —— 双指针法的高效应用” 的相关文章

c#中string和StringBuilder效率对比

c#中string和StringBuilder效率对比

    c#中string和StringBuilder直接看看执行速度。(2).String类型累计赋值Test               ...

svn自动更新到网站

svn自动更新到网站

【一】.钩子文件的设置和创建(1).打开hooks目录,可以看到有一个post-commit.tmpl文件,这是一个模板文件。复制一份,重命名为post-commit,将其用户组设为www,并设置为可执行。chown www:www post-commitchmod +x post-commit(2...

Git本地仓库学习

Git本地仓库学习

1.全局用户信息设置 git  config  --global  user.name  gaojiufeng git  config  --global  user.email  392223903...

Application的错误使用

Application的错误使用

Application 对象用于存储和访问来自任意页面的变量,类似 Session 对象。不同之处在于所有的用户分享一个 Application 对象,而 session 对象和用户的关系是一一对应的。很多的书籍中介绍的Application对象都喜欢以统计在线人数来介绍Application 对象...

Git推送文件到远程仓库

Git推送文件到远程仓库

1.远程仓库的协作模式开发者把自己最新的版本推到线上仓库,同时把线上仓库的最新代码,拉到自己本地即可2.注册git帐号国外: http://www.github.com国内: http://git.oschina.net2.在码云创建项目,不要初始化readmegit push https://gi...

C# md5加密,C# md5加密代码

C# md5加密,C# md5加密代码

public static string GetMD5(string str) {     //创建MD5对象     MD5 md5 = MD5.C...