0011.盛水最多的容器

张开发
• 2026/4/21 3:10:19 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

0011.盛水最多的容器
题目链接11. 盛最多水的容器 - 力扣LeetCode题目描述给定一个长度为 n 的整数数组 height 。有 n 条垂线第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。题目示例示例 1 :输入[1,8,6,2,5,4,8,3,7] 输出49 解释图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下容器能够容纳水表示为蓝色部分的最大值为 49。示例 2 :输入height [1,1] 输出1解题思路left 指向最左边的数组, right 指向最右边的数组怎么去利用双指针找最大盛水量呢, 宽度为 right - left, 高度为 min(height[right], height[left])如果移动的话, 哪一个边比较小, 就去移动那个边题解代码Java 代码 :classSolution{publicintmaxArea(int[]height){intres0,left0,rightheight.length-1;while(leftright){// 面积 高 × 宽 (高要取最短的那条, 短板效应)intareaMath.min(height[left],height[right])*(right-left);resMath.max(area,res);// 收缩两边界if(height[left]height[right]){left;}else{right--;}}returnres;}}复杂度分析时间复杂度: 只需要一次遍历数组left和right指针各自向中间靠拢因此时间复杂度为 O(n)其中n是数组的长度。空间复杂度: 只使用了常数级别的额外空间主要是用来存储res、left和right因此空间复杂度为 O(1)。

更多文章