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

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.length
function 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

秒客网

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

O(n^2)

O(nlogn)

O(n)

相关文章