网站信息做参考文献,dede做双语网站,网站描述优化,注册网站能赚钱吗原题地址#xff1a;. - 力扣#xff08;LeetCode#xff09; 题目描述#xff1a; 给定一个长度为 n 的整数数组 height 。有 n 条垂线#xff0c;第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线#xff0c;使得它们与 x 轴共同构成的容器可以容纳… 原题地址. - 力扣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.length2 n 1050 height[i] 104 解题思路 我们使用两个指针 l 和 r 分别指向数组的两端l 从左往右移动r 从右往左移动。在每一步中我们计算当前指针所指位置形成的矩形面积这个矩形的宽度是 r - l高度是 height[l] 和 height[r] 中的较小值因为水的深度不能超过这两个高度中的较小者。我们更新答案 ans 为当前计算的面积和之前答案中的最大值。然后我们根据 height[l] 和 height[r] 的大小决定指针的移动方向。如果 height[l] 小于等于 height[r]则增加 l因为增加 l 可以增加矩形的宽度并且不会减少矩形的高度。反之如果 height[l] 大于 height[r]则减少 r。这个过程一直持续到两个指针相遇此时我们已经考虑了所有可能的矩形并且找到了能够容纳最大雨水量的矩形 实现源码
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)因为我们只使用了常数个额外的变量来存储指针和最大面积不依赖于输入数组的大小。
