题目描述11. 盛最多水的容器 - 力扣LeetCode解题思路这道题很容易想到双指针的解法但真正核心的是想到指针该怎么转移。核心转移的思路其实只有一句话水桶在越来越窄的情况下只有换短板才有可能通过增加高度从而增加盛水量。根据这句话我们就可以把左指针放在在数组最左端右指针在数组最右端。容器盛水面积 两个柱子中较矮的高度 × 两指针之间的距离。每次计算当前面积并更新最大值哪边柱子高度更小就移动哪边的指针。因为容器的高度受限于矮柱子如果移动高的那一侧宽度变小高度不会增加面积只会更小移动矮柱子才有可能遇到更高的柱子得到更大面积。遍历一次即可完成时间复杂度 O (n)。代码如下class Solution { public: int maxArea(vectorint height) { int l0,rheight.size()-1; // 左右双指针分别指向首尾 int ans0; while(lr) { // 计算当前容器面积取矮的柱子 * 宽度(r‑l)更新最大面积 ansmax(ans,min(height[l],height[r])*(r-l)); if(height[l]height[r]){ l; // 左边更矮左指针右移尝试找更高柱子 }else{ r--; // 右边更矮右指针左移 } } return ans; } };时间复杂度O(n)只遍历一遍数组即可。空间复杂度O(1)。这道题核心点就在移动矮的那边。 LeetCode 热题100 No.5——盛最多水的容器
题目描述11. 盛最多水的容器 - 力扣LeetCode解题思路这道题很容易想到双指针的解法但真正核心的是想到指针该怎么转移。核心转移的思路其实只有一句话水桶在越来越窄的情况下只有换短板才有可能通过增加高度从而增加盛水量。根据这句话我们就可以把左指针放在在数组最左端右指针在数组最右端。容器盛水面积 两个柱子中较矮的高度 × 两指针之间的距离。每次计算当前面积并更新最大值哪边柱子高度更小就移动哪边的指针。因为容器的高度受限于矮柱子如果移动高的那一侧宽度变小高度不会增加面积只会更小移动矮柱子才有可能遇到更高的柱子得到更大面积。遍历一次即可完成时间复杂度 O (n)。代码如下class Solution { public: int maxArea(vectorint height) { int l0,rheight.size()-1; // 左右双指针分别指向首尾 int ans0; while(lr) { // 计算当前容器面积取矮的柱子 * 宽度(r‑l)更新最大面积 ansmax(ans,min(height[l],height[r])*(r-l)); if(height[l]height[r]){ l; // 左边更矮左指针右移尝试找更高柱子 }else{ r--; // 右边更矮右指针左移 } } return ans; } };时间复杂度O(n)只遍历一遍数组即可。空间复杂度O(1)。这道题核心点就在移动矮的那边。 RELATED READING
延伸阅读
更多一线实战笔记与深度复盘，助您持续精进
