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

盛水最多的容器问题详解：双指针法与暴力法的对比与实现

news 来源：原创 2025/8/26 14:39:47

文章目录

- 问题描述
- 方法探讨
- - 方法一：暴力法（Brute Force）
  - - 思路
    - 代码实现
    - 复杂度分析
  - 方法二：双指针法（Two Pointers）
  - - 思路
    - 正确性证明
    - 代码实现
    - 复杂度分析
- 方法对比
- 总结

摘要
盛水最多的容器（Container With Most Water）是LeetCode上一道经典的算法题，考察对数组和双指针技巧的应用。本文将详细分析问题的核心思路，探讨暴力法和双指针法两种实现方法，并对比它们的性能差异。通过代码实现和复杂度分析，帮助深入理解如何高效解决此类问题。

问题描述

11. 盛最多水的容器
在这里插入图片描述

方法探讨

方法一：暴力法（Brute Force）

思路

暴力法是最直接的思路：遍历所有可能的线对组合，计算每对线构成的容器容量，记录最大值。

代码实现

public class Solution {public int maxAreaBruteForce(int[] height) {int maxArea = 0;for (int i = 0; i < height.length; i++) {for (int j = i + 1; j < height.length; j++) {int currentHeight = Math.min(height[i], height[j]);int currentWidth = j - i;maxArea = Math.max(maxArea, currentHeight * currentWidth);}}return maxArea;}
}

复杂度分析

时间复杂度：O(n²)，需要两重循环遍历所有可能的线对。
空间复杂度：O(1)，仅使用常数级额外空间。

缺点
当数组长度较大时（如 n=10^5），暴力法会超时，无法处理大规模数据。

方法二：双指针法（Two Pointers）

思路

双指针法通过一次遍历高效解决问题，核心思想是缩减搜索空间：

初始化指针：左指针 left 指向数组起始位置，右指针 right 指向数组末尾。
计算容量：当前容量由 min(height[left], height[right]) * (right - left) 决定。
移动指针：每次移动高度较小的指针（因为移动较高的指针不会增加容量）。
更新最大值：比较并记录最大容量。

正确性证明

假设当前左右指针高度分别为 h[left] 和 h[right]，且 h[left] < h[right]。此时若固定 left，无论 right 如何左移，新的容量一定小于当前容量（因为宽度减小，高度不超过 h[left]）。因此，必须移动左指针才有可能找到更大的容量。

代码实现

public class Solution {public int maxArea(int[] height) {int left = 0, right = height.length - 1;int maxArea = 0;while (left < right) {int currentHeight = Math.min(height[left], height[right]);int currentWidth = right - left;maxArea = Math.max(maxArea, currentHeight * currentWidth);// 移动较低的一侧指针if (height[left] < height[right]) {left++;} else {right--;}}return maxArea;}
}

复杂度分析

时间复杂度：O(n)，只需一次遍历。
空间复杂度：O(1)。

方法对比

方法	时间复杂度	空间复杂度	适用场景
暴力法	O(n²)	O(1)	小规模数据
双指针法	O(n)	O(1)	大规模数据

总结

暴力法虽然简单直观，但效率低下，仅适用于学习阶段的小规模数据验证。
双指针法通过缩小搜索空间将复杂度降至线性级别，是解决此问题的标准方法。
关键思路：移动较低一侧的指针，确保不会错过更大容量的可能性。

拓展思考
双指针法还可以用于解决其他类似问题，如“接雨水”（Trapping Rain Water）从暴力到动态规划再到双指针：使用 Java 探索接雨水问题的不同解法。理解其核心思想有助于举一反三，应对更多复杂场景。

文章目录

问题描述

方法探讨

方法一：暴力法（Brute Force）

思路

代码实现

复杂度分析

方法二：双指针法（Two Pointers）

思路

正确性证明

代码实现

复杂度分析

方法对比

总结

相关文章：