当前位置: 首页> 健康> 知识 > 成都人高清影院品牌加盟_长沙房产_网站优化员seo招聘_sem是什么意思

成都人高清影院品牌加盟_长沙房产_网站优化员seo招聘_sem是什么意思

时间:2025/7/10 2:46:52来源:https://blog.csdn.net/qq_36070104/article/details/143266573 浏览次数:0次
成都人高清影院品牌加盟_长沙房产_网站优化员seo招聘_sem是什么意思

原题地址:. - 力扣(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

提示:

  • n == height.length
  • 2 <= n <= 105
  • 0 <= height[i] <= 104

解题思路:

  1. 我们使用两个指针 l 和 r 分别指向数组的两端,l 从左往右移动,r 从右往左移动。
  2. 在每一步中,我们计算当前指针所指位置形成的矩形面积,这个矩形的宽度是 r - l,高度是 height[l] 和 height[r] 中的较小值,因为水的深度不能超过这两个高度中的较小者。
  3. 我们更新答案 ans 为当前计算的面积和之前答案中的最大值。
  4. 然后,我们根据 height[l] 和 height[r] 的大小决定指针的移动方向。如果 height[l] 小于等于 height[r],则增加 l,因为增加 l 可以增加矩形的宽度,并且不会减少矩形的高度。反之,如果 height[l] 大于 height[r],则减少 r
  5. 这个过程一直持续到两个指针相遇,此时我们已经考虑了所有可能的矩形,并且找到了能够容纳最大雨水量的矩形

实现源码:

class Solution {public int maxArea(int[] height) {// 初始化左右指针int l = 0, r = height.length - 1;// 初始化最大面积为0int ans = 0;// 当左指针小于右指针时,循环继续while (l < r) {// 计算当前指针所指位置形成的矩形面积int area = Math.min(height[l], height[r]) * (r - l);// 更新最大面积ans = Math.max(ans, area);// 如果左边的高度小于等于右边的高度,移动左指针if (height[l] <= height[r]) {++l;}// 否则,移动右指针else {--r;}}// 返回最大面积return ans;}
}

复杂度分析:

时间复杂度分析:

  • 这个算法的时间复杂度是 O(n),其中 n 是数组 height 的长度。这是因为我们只需要遍历一次数组,每次移动指针 l 或 r 一次。

空间复杂度分析:

  • 这个算法的空间复杂度是 O(1),因为我们只使用了常数个额外的变量来存储指针和最大面积,不依赖于输入数组的大小。
关键字:成都人高清影院品牌加盟_长沙房产_网站优化员seo招聘_sem是什么意思

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: