LeetCode 11.盛最多水的容器(左右对撞双指针)
)
class Solution { public int maxArea(int[] height) { //1.暴力求解法超出时间限制 // int maxArea 0; // for(int i 0; i height.length; i) { // for(int j i1; j height.length; j) { // int wide j - i; // int area wide * Math.min(height[i],height[j]); // maxArea Math.max(maxArea,area); // } // } //2.左右对撞双指针 int left 0, right height.length-1; int maxArea 0; while(left right) { int wide right - left; int area wide * Math.min(height[left], height[right]); if(height[left] height[right]) { left; }else { right--; } maxArea Math.max(maxArea, area); } return maxArea; } }一、核心算法思路采用左右对撞双指针时间复杂度 O (n)容器面积公式面积 宽度 × 两侧柱子较小高度水位由更矮的柱子决定短板效应左指针 left 放在数组最左端右指针 right 放在数组最右端初始宽度最大计算当前两根柱子围成的面积更新全局最大面积核心收缩规则向内移动高度更小一侧的指针。若移动高柱子宽度缩小、高度上限不变面积只会更小移动矮柱子才有机会遇到更高柱子得到更大面积不断收缩区间直到左右指针相遇最终返回最大面积。实例运行顺序演示测试输入height [1,8,6,2,5,4,8,3,7]初始状态left 0right 8maxArea 0leftrightheight[left]height[right]宽度当前面积maxArea操作0817888左边矮left188774949右边矮right--178361849右边矮right--168854049等高right--158441649右边矮right--148531549右边矮right--13822449右边矮right--12861649右边矮right--循环结束left right最终最大面积49二、语法 概念理解困惑点整理两种双指针区分 左右对撞双指针left 从头、right 从尾向中间靠拢本题、两数之和 II 快慢同向双指针left、right 同时从起点向右遍历283 移动零。三、踩坑清单收缩指针逻辑写反 错误移动更高一侧的柱子。宽度缩小水位上限不变不可能得到更大面积算法失效。循环条件写错 错误left right。指针相遇时宽度为 0面积为 0无计算意义条件应为left right。暴力双层循环隐患 双重 for 枚举所有组合复杂度 O (n²)测试用例数据量大时会超时面试不推荐。等高时不知道移动哪边 左右柱子高度相等left 或者 right-- 均可不影响最终结果。四、高频易混知识点面积本质限制因素容器储水高度由两根柱子矮者决定不是高柱子双指针优化原理利用面积数学规律舍弃大量不可能更优的组合把 O (n²) 优化到 O (n)数组属于引用类型本题只读取数组数值不需要修改原数组。
)
