水最多的储物容器
水最多的储物容器
提问于 2019-11-16 06:52:56
我在做容器时，使用的是Leetcode中的大多数水问题，为此我编写了这个算法。
问题链接：https://leetcode.com/problems/container-with-most-water
问题：
给定n个非负整数a1，a2，.，a，其中每个表示一个坐标点(i，ai).绘制n条垂直线，使线I的两个端点位于(i，ai)和(i，0)处。找出两条线，与x轴一起形成一个容器，这样容器中的水就最多了。注意:您不能倾斜容器，并且n至少是2。
输入：1,8,6,2,5,4,8,3,7
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
let currentHighest=0
while(height.length) {
const num = height.shift()
let j=0
while(j<height.length) {
const lowerNum = Math.min(num, height[j])
const distance = j+1
const area = distance * lowerNum
currentHighest = Math.max(currentHighest, area)
j++
}
}
return currentHighest
};但是看起来这段代码没有被优化，有人能帮我优化上面的代码吗？
回答 1
Code Review用户
发布于 2019-11-16 08:43:22
好的，所以我的实现非常类似于您的实现，通过以下修改：
- 输入没有被销毁(尽管它仍然可以调整以销毁它，但它只是觉得这样的算法不应该这样做)。
- 当我从左边迭代时，我计算了值的最大潜在容器区域。
- 我从末端循环到前面。
- 我利用这个潜力来减少内循环的迭代次数。
function maxArea (input)
{
// result value will go here
let currentMax = 0;
// we will need this value at least 2*(n-1) times:
const limit = input.length - 1;
// i<limit because having i=limit would always yield zero size container so skip it:
for(let i = 0; i < limit; ++i) {
const left = input[i];
// zero size edge always yields zero size container so move to next i
// this check may be omitted as the next will exclude it as well
//if (left == 0) continue;
// the largest container we can have on the right has this area:
let potential = left * (limit - i);
// if potential is not enough to get over currentMax, just move to next i
if (potential <= currentMax) continue;
// search from end towards i becase more distant j is more likely to yield larger container and only the last j can actualy yield current potential
for (let j = limit; j > i; --j) {
const right = input[j];
// if right is at least as high as left then this container has the area equal to potential and no other j will do better for current left value
if (right >= left) {
currentMax = potential;
break;
}
// if it is smaller we check if its area is greater then currentMax and use it if it is
const area = right * (j - i);
if (area > currentMax) currentMax = area;
//decrease potential by 1 times left value because we will reduce distance by 1 for next iteration (--j):
potential -= left;
// if new potential is not enough to get over currentMax we can stop searching further j's and move to next i
if (potential <= currentMax) break;
}
}
return currentMax;
}结果表明，该算法在时间和空间上仍然是O(n^2)和O(1)。但我相信这比你的要好。而且(不像您的)实际性能对于不同的输入值是不同的，而不仅仅是对于不同长度的输入数组。在最坏情况下(即严格递减序列)和实际O(n)在最佳情况下(即增加序列)是一样的。当然，对于大多数可能的输入值的变化，两者之间的任何地方。
编辑:呵呵，我把它安放在随机的100 k值数组上，我的大约花费4ms，你的15+秒:)最坏的情况是你的15秒，我的7秒。但是最坏的情况是所有可能性的集合都很小，所以从随机性中获得它是不可能的。随机性只适用于少数ms。因此，对于随机的100 k值输入，按几千倍的改进:)
页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://codereview.stackexchange.com/questions/232488
复制相关文章
相似问题
腾讯云开发者
