凌美上海建设工程网站,网站建设报价分析,青岛公司,wordpress首页只显示文章摘要1.问题描述 给定一个长度为 n 的整数数组 height 。有 n 条垂线#xff0c;第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线#xff0c;使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量 注意 你不能倾斜容器 示例1 输入第 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 难度等级 中等 题目链接 盛最多水的容器
2.解题思路 这道题是让我们在其中找出盛水最多的容器我们先来简单的分析一下。容器能盛多少水取决于它的宽度和高度我们可以定义两个指针从数组的左右两边向中间移动也就是一开始假设宽度是最大的然后在左右指针不断移动的过程中寻找容器所能盛的最多的水。 //竖直方向容纳多少水取决于最短的高度//水平方向容纳多少水取决于最大的差值int head 0;int tail height.length-1;int result 0; 容器的高度取决于左右指针的较小值容器的宽度为左右指针索引的差值宽*高之后与目前记录的最大值比较若比最大值大则更新最大值。 //宽度int w tail - head;//取短边作为高度int h height[head] height[tail] ? height[head] : height[tail];//更新最大值result h * w result ? h * w : result; 接着移动较小边的指针因为我们要盛尽可能多的水就必须让高尽可能的大接着重复上述操作知道指针相遇退出循环。 //移动短边的指针if(height[head] height[tail]){head;}else{tail--;}
3.代码展示
class Solution {public int maxArea(int[] height) {//竖直方向容纳多少水取决于最短的高度//水平方向容纳多少水取决于最大的差值int head 0;int tail height.length-1;int result 0;while(head tail){//宽度int w tail - head;//取短边作为高度int h height[head] height[tail] ? height[head] : height[tail];//更新最大值result h * w result ? h * w : result;//移动短边的指针if(height[head] height[tail]){head;}else{tail--;}}return result;}
}
4.总结 这道题我觉得唯一难的地方就是能不能想到一开始假设两个条件中的宽最大左右指针从数组左右两边向中间靠拢其他的地方我感觉没啥太大的难度。祝大家刷题愉快
