怎么做网站推广毫州,网站源代码安装,wordpress修改网站菜单位置,四川省第十五公司官网文章收录于LeetCode专栏 盛最多水的容器 给你n个非负整数a1#xff0c;a2#xff0c;…#xff0c;an#xff0c;每个数代表坐标中的一个点(i, ai) 。在坐标内画 n 条垂直线#xff0c;垂直线i的两个端点分别为(i, ai) 和 (i, 0)。找出其中的两条线#xff0c;使得它们与… 文章收录于LeetCode专栏 盛最多水的容器 给你n个非负整数a1a2…an每个数代表坐标中的一个点(i, ai) 。在坐标内画 n 条垂直线垂直线i的两个端点分别为(i, ai) 和 (i, 0)。找出其中的两条线使得它们与x轴共同构成的容器可以容纳最多的水。 说明你不能倾斜容器。 示例 1 输入[1, 8, 6, 2, 5, 4, 8, 3, 7] 输出49 解释图中垂直线代表输入数组[1,8,6,2,5,4,8,3,7]。在此情况下容器能够容纳水表示为蓝色部分的最大值为49 解题
1、审题 数组中各个元素表示柱子的高度坐标系中的纵坐标这里的高度就可以作为容器的高两跟柱子之间的间距就作为容器的长即容器最多容纳水就是高乘以长。要把柱子的高作为容器的高就会必须得取二则的相对矮的那一根柱子。例如1和8之间就得取1。
2、列出所有解 通过对题意的理解可以使用暴力法和左右收敛法来解答改题目。
解法一暴力法
class Solution{public int maxArea(int[] height){int max 0;for(int i0; iheight.length-1; i){for(int ji1; jheight.length; j){int area Math.min(height[i], height[j]) * (j-i);max Math.max(max, area);}}return max;}
}解法二左右收敛
class Solution{public int maxArea(int[] height){int max 0;for(int i0, jheight.length-1; ij;){int h height[i] height[j] ? height[i]:height[j--];int area h * (j-i1);max Math.max(max, area);}return max;}
}3、复杂度分析 首先来看下暴力解法的时间复杂度和空间复杂度因为暴力法使用了两层循环所以时间复杂度为O(n2)没有使用任何额外空间所以空间复杂度为O(1)。左右收敛法因为只使用一层循环所以时间复杂度为O(n)同样空间复杂度为O(1)。综上左右收敛法是最优解。 一键三连让我的信心像气球一样膨胀
