双指针巧解最大水容器（Python，Java，C语言三解法）

题目给定一个长度为n的整数数组height。有n条垂线第i条线的两个端点是(i, 0)和(i, height[i])。找出其中的两条线使得它们与x轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。输入[1,8,6,2,5,4,8,3,7]输出49解释图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下容器能够容纳水表示为蓝色部分的最大值为 49Python解法代码示例class Solution: def maxArea(self, height: List[int]) - int: left 0 right len(height) - 1 max_water 0 while left right: h min(height[left],height[right]) w right - left current h * w if current max_water: max_water current if height[left] height[right]: right - 1 else : left 1 return max_water解释1首先进行初始化。left左指针从最左边开始right右指针从最右边开始max_water记录最大水量left 0 right len(height) - 1 max_water 02写明循环条件展示逻辑。只要两个指针没相遇就继续h高度 两根里矮的那个w宽度 右 - 左current当前能装的水量while left right: h min(height[left],height[right]) w right - left current h * w3如果当前更大就更新最大值。if current max_water : max_water current4移动指针策略。核心贪心只动矮的才有机会变大左边矮小左指针右移右边矮小右指针左移if height[left] height[right]: right - 1 else: left 1过程展示height [1,8,6,2,5,4,8,3,7] 0 1 2 3 4 5 6 7 8 初始: left0(高1), right8(高7) 面积 min(1,7) * 8 8 17, 移动left → left1 left1(高8), right8(高7) 面积 min(8,7) * 7 49 ✓ 当前最大 87, 移动right → right7 ...继续直到相遇Java解法代码示例(解释在代码块中)class Solution { /* * 双指针法求最大水容器面积 * 时间复杂度: O(n)空间复杂度: O(1) */ public int maxArea(int[] height) { // 初始化双指针分别指向数组两端 int left 0; int right height.length - 1; int maxArea 0; while (left right){ // 面积 高度两边最小值× 宽度距离 int currentHeight Math.min(height[left],height[right]); int width right - left; int currentArea currentHeight * width; // 保留最大面积 maxArea Math.max(maxArea, currentArea); // 关键移动较短的那一边 // 原理移动长边min值不会变大宽度减小面积只会更小 if (height[left] height[right]){ left; }else{ right--; } } return maxArea; } }C语言解法代码示例解释在代码块中int maxArea(int* height, int heightSize) { // 初始化双指针 int left 0; // 左指针从开头 int right heightSize - 1; // 右指针从末尾 int maxArea 0; // 记录最大面积 while (left right) { // 计算当前容器的高度短板决定水位 int minHeight height[left] height[right] ? height[left] : height[right]; int width right - left; int area minHeight * width; // 保留最大值 maxArea area maxArea ? area : maxArea; // 核心移动较短的那一边 // 原因移动长边min值不会增加宽度减小面积必然减小 // 移动短边虽然宽度减小但高度可能增加面积可能增大 if (height[left] height[right]) { left; // 左边短左指针右移 } else { right--; // 右边短或相等右指针左移 } } return maxArea; }总结核心思路初始状态用两个指针分别指向数组最左端和最右端此时宽度最大贪心选择每次移动高度较小的指针容器高度由较矮的柱子决定移动较高的柱子只会让宽度变小无法增加水量。移动较矮的柱子才有机会遇到更高的柱子从而让总水量变大。终止条件两指针相遇left right遍历结束。