文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析2、解题代码三、知识风暴前言本专栏文章为《LeetCode 热题 100》的刷题题解相关内容如有侵权立即删除。一、题目1、原题链接11.盛最多水的容器2、题目描述二、个人思路整理1、思路分析核心思路是对向双指针贪心策略。容器容纳的水量公式为Area ( r − l ) × min ⁡ ( h e i g h t [ l ] , h e i g h t [ r ] ) \text{Area} (r - l) \times \min(height[l], height[r])Area(r−l)×min(height[l],height[r])移动策略每次比较左右两边固定较长的一边向内移动较短的那一边。为什么不能移动长边如果移动长边底边宽度r − l r - lr−l必定减小而容器的高度受限于原来的短边最多只能维持原短边的高度甚至更低。因此面积必定严格减小。移动长边不可能产生更优解。为什么移动短边才可能更优虽然宽度变小但如果移动后的新柱子比原短边更高容器的有效高度可能会提升从而有机会获得更大的面积。终止条件当两指针相遇lr时遍历结束期间记录的最大面积即为全局最优解复杂度分析时间复杂度O ( n ) O(n)O(n)双指针各向中间移动一次整体遍历一遍数组。空间复杂度O ( 1 ) O(1)O(1)仅使用常数级额外空间。2、解题代码classSolution{public:intmaxArea(vectorintheight){// 初始化双指针left指向数组首端right指向数组尾端// 初始化下底边宽度(right - left)最大intleft0,rightheight.size()-1;// 记录遍历过程中出现的最大盛水量intmax_water0;// 当左右指针相遇时循环终止while(leftright){// 容器的容水量公式底边宽度 * 两端较矮柱子的高度木桶效应intcurrent_water(right-left)*min(height[left],height[right]);// 更新全局最大容水量max_watermax(max_water,current_water);// 贪心策略移动较矮的那一侧指针// 原因// 1. 若移动较长边底边宽度变小而容器高度受限于原短边不可能超过短边面积必定减下。// 2. 若移动较短边虽然宽度减小但新柱子有可能更高从而带来面积增大的可能。if(height[left]height[right]){left;// 左侧较矮左指针右移寻找更高的柱子}else{right--;// 右侧较矮或两者等高右指针左移寻找更高的柱子}}returnmax_water;}};三、知识风暴对向双指针Two Pointers本质利用单调性排除无效状态将O ( n 2 ) O(n^2)O(n2)暴力穷举优化至O ( n ) O(n)O(n)。适用区间边界最值面积/容量、有序数组查找两数之和。贪心突破短板短板效应Area ( r − l ) × min ⁡ ( h l , h r ) \text{Area} (r - l) \times \min(h_l, h_r)Area(r−l)×min(hl​,hr​)面积由较矮边决定。移动策略宽度必然减小移动长边必变小移动短边才可能变大。