WEB前端

当前位置:首页 > 技术世界 > WEB前端

如何装最多的水? — leetcode 11. Container With Most Water

炎炎夏日,还是呆在空调房里切切题吧。

Container With Most Water,题意其实有点噱头,简化下就是,给一个数组,恩,就叫 height 吧,从中任选两项 i 和 j(i <= j),使得 Math.min(height[i], height[j]) * (j - i) 最大化,求解这个最大值。

O(n^2)

O(n^2) 复杂度的解法非常容易想到,直接两两枚举。

var maxArea = function(height) {  var len = height.length;  var maxn = 0;  for (var i = 0; i < len; i++)    for (var j = i + 1; j < len; j++)      maxn = Math.max(maxn, Math.min(height[i], height[j]) * (j - i));  return maxn;};

提交,TLE,看了下数据,数组长度 1w,复杂度直接飙到亿级,不 TLE 才怪了。

O(nlogn)

我们假设数组为 [a1, a2, ..., an],我们实际需要求得的其实是一个子数组。假设这个子数组的最后一个元素是 a5,同时我们规定该子数组最后一个元素不大于第一个元素,那么实际我们需要求的是 a1, a2, a3, a4 中哪个元素比 a5 大(或者相同),并且这个元素越前面越好。

这样,我们可以遍历每个元素,将这个元素确定为子数组的最后一个元素,同时去求前面已经被遍历过的元素中,大于等于该元素并且最左的元素。对于求这个最左元素,我们可以维护一个单调递增的数组,用二分去解。

二分需要求解一个递增序列中,刚好大于等于指定元素的位置,这个 case 没有出现在 二分查找大集合(妈妈再也不用担心我的二分查找了),我们可以稍微变个形。

// 求解 a 数组中刚好大于等于 target 的位置// 如果都小于 target 则返回 a.lengthfunction binarySearch(a, target) {  target += 1;  var start = 0    , end = a.length - 1;  while(start <= end) {    var mid = ~~((start + end) >> 1);    if (a[mid] >= target)      end = mid - 1;    else      start = mid + 1;  }  if (a[start - 1] === target - 1)    start -= 1;  return start;}

还需要注意的一点是,必须正反来两次,因为我们假设子数组的最后一个元素小于等于首元素,还需要考虑另一种情况,即子数组首元素小于等于最后一个元素。

其他部分问题不大,具体代码可以参考 https://github.com/hanzichi/leetcode/blob/master/Algorithms/Container%20With%20Most%20Water/O(nlogn).js

提交,AC,击败 4% ... 势必还有更优的解法,而且根据我的经验,如果这是标程正解的话,这道题的难度应该是 Hard 而不是 Medium 了。

O(n)

正解的复杂度应该是 O(n) 的。

我们可以举个简单的例子,假设数组是 [2, 3, 4, 5, 4, 3],那么最长的子数组一定只有一个,即取全部元素,这样能装的水的数量是 2 * 5 。接下去我们的子元素,长度一定是会变小的,有两种情况,为 [2, 3, 4, 5, 4][3, 4, 5, 4, 3]。我们来看 [2, 3, 4, 5, 4],这种情况下,显然比取全部元素求得的结果 10 要小,为什么这么说?因为两者的基准都是按 2 来算的,但是取全部元素长度大。

似乎有点眉目了,再来看 [2, 3, 4, 5, 4, 3] 这个原始的数组,从中找出一个子数组,如果以 2 为子数组最左的元素,那么这个子数组求解的值(即装水的量),不可能比 [2, 3, 4, 5, 4, 3] 这个原始数组求到的 10 要大了,有木有?!因为该子数组装水的基准,是不可能比 2 大了的。

这样,我们似乎可以用一点点贪心去解这道题,一步步缩小子数组的大小。

while (start <= end) {  maxn = Math.max(maxn, Math.min(height[end], height[start]) * (end - start));  if (height[end] < height[start])    end --;  else    start ++;}

完整代码可以参考 https://github.com/hanzichi/leetcode/blob/master/Algorithms/Container%20With%20Most%20Water/O(n).js

转载说明:欢迎转载本站所有文章,如需转载请注明来源于《绝客部落》。

本文链接:https://juehackr.net/qianduan/125.html

相关内容

文章评论

表情

共 0 条评论
  • 这篇文章还没有收到评论,赶紧来抢沙发吧~