力扣(11) - day02

11. 盛最多水的容器

​ 给定整数数组 height，数组元素代表垂直于 x 轴的线段高度，要找出两条线段，与 x 轴构成容器，求能容纳最多水的容量（水容量 = 两条线段中较矮的高度 × 线段间水平距离 ）。

解题思路

一、双指针法（用双指针从数组两端向中间遍历，动态调整指针位置，计算并更新最大容量）

1. 指针初始化：左指针 left 指向数组起始（索引 0 ），右指针 right 指向数组末尾（索引 height.length - 1 ）。

   int maxArea = 0, left = 0, right = height.length - 1;

2. 容量计算与更新：每次取 left 和 right 对应高度的较小值（决定容器高度，因为水会从矮的一侧溢出 ），乘以指针间距（水平距离 ），得到当前容器容量，再和历史最大容量 maxArea 比较，更新 maxArea。

   maxArea = Math.max(maxArea, Math.min(height[left], height[right]) * (right - left));

3. 指针移动策略：若 height[left] < height[right]，说明左指针对应的线段更矮，固定右指针时，左指针右移可能找到更高线段，让容量更大，所以 left++；反之，right-- 。重复此过程，直到 left >= right ，遍历结束，此时 maxArea 就是最大容量。

   if (height[left] < height[right]) {left++; } else { // 否则，左移右指针，尝试找更高的右边界 right--; }

完整代码

class Solution { public int maxArea(int[] height) { int maxArea = 0, left = 0, right = height.length -1; while(left < right){ maxArea = Math.max(maxArea,Math.min(height[left],height[right])*(right-left)); if(height[left] < height[right]){ left ++ ; }else{ right --; } } return maxArea; }}

二、暴力遍历法（遍历所有可能的线段对，计算每对线段构成的容器容量，并记录最大值）

1. 双重循环遍历所有线段对

2. 容量计算与更新：对于每对线段 i 和 j，计算其容量（取两线段高度的最小值乘以它们之间的距离），并与当前记录的最大容量 maxArea 比较，若更大则更新 maxArea。

   maxArea = Math.max(maxArea, Math.min(height[i], height[j]) * (j - i));

3. 返回结果：遍历结束后，maxArea 即为所有可能的容器中最大的容量。

完整代码

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

注意：时间复杂度为O(n^2)，在处理大量数据时，可能会存在超时。