11. Container With Most Water

Leetcode link

解题思路

本题要求我们选中任意两个高度当成容器求水的最大体积。由题目可知，水的体积 S 的公式如下：

S = (right - left) * min(height[left], height[right])，其中 left 与 right 分别是选中的两个高度的下标。

如果把所有的情况遍历一次，总共需要 n * (n - 1) / 2 次，肯定不符合预期，所以我们必须想办法减少复杂度。

考虑到如下两种情况：

• height[left] < height[right]：我们接下来只需要检查 (left + 1, right) 这个区间就好
• height[right] <= height[left]：我们接下来只需要检查 (left, right - 1) 这个区间就好

证明：假设 height[left] < height[right]，我们来证明 (left, right - X) 区间已经没有任何能增加水体积的可能了。

当X = 1 时，在区间 (left, right - 1) 我们有水体积 S' = (right - 1 - left) * min(height[left], height[right - 1])。

从 S' <= (right - 1 - left) * height[left] < (right - left) * height[left] = S 可以推导出 S' < S，可想而知，就算 X 再大，只会让水体积更小

在上述结论的情况下，我们再进一步思考，在 height[left] < height[right] 的时候，如果 height[left + 1] 还是小于 height[left] 那就可以直接略过这个直接检查 left + 2、 left + 3…… 直到找到第一个 height[left + X] > height[left] 之后再计算水体积进行比较。

C++

class Solution {
 public:
  int maxArea(vector<int>& height) {
    int result = 0, left = 0, right = height.size() - 1;
    while (left < right) {
      int h = min(height[left], height[right]);
      result = max(result, h * (right - left));
      // 如果换了的高度比原来还低就没必要比较了，进一步减少计算量
      while (height[left] <= h && left < right) left++;
      while (height[right] <= h && left < right) right--;
    }
    return result;
  }
};

Javascript

var maxArea = function(height) {
    let result = 0, left = 0, right = height.length - 1;
    while (left < right) {
      let h = Math.min(height[left], height[right]);
      result = Math.max(result, h * (right - left));
      // 如果换了的高度比原来还低就没必要比较了，进一步减少计算量
      while (height[left] <= h && left < right) left++;
      while (height[right] <= h && left < right) right--;
    }
    return result;
};