摘要:题目解答这里如果左边的数比右边的数小,那么这就是取这个位置时的面积最大值。因为不管怎么向左移动,最大高度也还是的值,而宽只会减小。所以我们只有向右移动才有可能遇到更大的,从而有可能产生更大的面积。
题目:
Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container.
解答:
public class Solution { public int maxArea(int[] height) { int max = 0; int left = 0, right = height.length - 1; while (left < right) { max = Math.max(max, (right - left) * Math.min(height[left], height[right])); //这里如果左边的数比右边的数小,那么这就是取left这个位置时的面积最大值。因为不管right怎么向左移动,最大高度也还是height[left]的值,而宽只会减小。所以我们只有向右移动left才有可能遇到更大的height,从而有可能产生更大的面积。 if (height[left] < height[right]) { left++; } else { right--; } } return max; } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/66209.html
摘要:我们需要找出这些线所围成的容器,能装最多水的水量。这道题是不能用蛮力法解决的,会超时。这个解法想法是这样的,我们用两个变量,指向数组的起始元素和末尾元素。首先计算这两条线所围成的容器面积,然后移动指向较短的线段的指针。 题目详情 Given n non-negative integers a1, a2, ..., an, where each represents a point at...
摘要:一题目盛最多水的容器给定个非负整数,,,,每个数代表坐标中的一个点。在坐标内画条垂直线,垂直线的两个端点分别为和。找出其中的两条线,使得它们与轴共同构成的容器可以容纳最多的水。在此情况下,容器能够容纳水表示为蓝色部分的最大值为。 一、题目 盛最多水的容器: 给定 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i ...
摘要:最新更新请访问栈法复杂度时间空间思路最大盛水量取决于两边中较短的那条边,而且如果将较短的边换为更短边的话,盛水量只会变少。所以我们可以用两个头尾指针,计算出当前最大的盛水量后,将较短的边向中间移,因为我们想看看能不能把较短的边换长一点。 Container With Most Water 最新更新请访问:https://yanjia.me/zh/2018/11/... Given n...
摘要:题目要求给一个数组,其中数组在下标处的值为,坐标和坐标构成一条垂直于坐标轴的直线。现任取两条垂线和轴组成四边形容器。当左右指针相遇时,指针假设该算法并没有遍历到容量最大的情况我们令容量最大时的指针为和。 题目要求:给一个数组,其中数组在下标i处的值为A[i],坐标(i,A[i])和坐标(i,0)构成一条垂直于坐标轴x的直线。现任取两条垂线和x轴组成四边形容器。问其中盛水量最大为多少? ...
摘要:思路对撞指针问题,求最大体积,当缩小宽度时,则高度必须比原来大。两边指针选较小的一个靠近直到比原来的大。此程序实现中省略了内层。 http://www.lintcode.com/en/pr... Container with Most Water Given n non-negative integers a1, a2, ..., an, where each represents ...
阅读 867·2021-09-29 09:35
阅读 1229·2021-09-28 09:36
阅读 1494·2021-09-24 10:38
阅读 1039·2021-09-10 11:18
阅读 613·2019-08-30 15:54
阅读 2483·2019-08-30 13:22
阅读 1939·2019-08-30 11:14
阅读 674·2019-08-29 12:35