力扣HOT100-5 盛最多水的容器(Java实现)

题目

题目解读

1.木桶效应，短边决定蓄水量
2.选定i < j，水量 =(j - i) × min(height[i], height[j])

开始解题

一、暴力枚举

思路：

双重循环尝试所有组合(i, j)，计算面积并更新最大值。

核心流程：

1.初始化 maxArea = 0。

2.外层循环 i 从 0 到 n-2。

3.内层循环 j 从 i+1 到 n-1：

计算 area = (j - i) * min(height[i], height[j])。

maxArea = max(maxArea, area)。

4.返回 maxArea。

代码

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

二、双指针法

思路：

想要一次遍历找到最大水量，我们需要一种聪明的方式排除不可能成为答案的柱子组合。

初始时，左右指针放在数组两端（此时宽度最大）。对于当前的两根柱子，容器的水量取决于较矮的那根（短板效应）。
如果我们固定短板，向内移动另一根更高的柱子，宽度减小，但高度最大也只能是短板的高度，因此面积不可能增大。
因此，唯一可能得到更大面积的方法，就是向内移动短板，虽然宽度变小，但有可能遇到更高的短板，从而抬高水位。

所以策略是：每次计算当前面积后，移动高度较小的那个指针。当两个指针相遇时，所有可能的最优解都已被检视过。

核心流程：

1.初始化 left = 0, right = n - 1, maxArea = 0。
2.当 left < right 时循环：
计算当前面积 area = (right - left) * min(height[left], height[right])。
更新 maxArea = max(maxArea, area)。
若 height[left] < height[right]，则 left++；否则 right--。
3.返回 maxArea。

代码

public int maxArea(int[] height) { int left = 0, right = height.length - 1; int maxArea = 0; while (left < right) { int minH = Math.min(height[left], height[right]); int area = (right - left) * minH; maxArea = Math.max(maxArea, area); // 移动较短的那边 if (height[left] < height[right]) { left++; } else { right--; } } return maxArea; }

感谢您能够看到这里，一起见证小何同学的算法学习，如果您有不同的见解，希望能得到您的指点和点悟；如果您是和我一样的同学，也希望这篇文章能对您有所帮助。