maxArea

11. 盛最多水的容器

算法

容器的水量由两条垂线的较小高度和它们之间的水平距离决定，公式为：min(height[i], height[j]) * (j - i)

初始时，将左右指针分别置于数组的两端
计算当前两条垂线能容纳的水量，并更新最大水量
移动高度较小的一侧的指针：
- 因为容器的水量由两条垂线的较小高度决定，移动较小高度的一侧可能增加更高的高度，从而得到更大的水量
当左右指针相遇时，遍历结束，最大水量即为结果

复杂度分析

时间复杂度

指针遍历：每次移动一个指针，最多遍历数组一次，时间复杂度为 O(n)

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution
    {
public:
    int maxArea(vector<int>& height)
    {
        int res = 0; // 存储最大水量
        int i = 0, j = height.size() - 1; // 初始化左右指针

        while (i < j)
        {
            // 计算当前容器的水量
            res = std::max(res, std::min(height[i], height[j]) * (j - i));

            // 移动高度较小的一侧
            if (height[i] < height[j]) ++ i;
            else -- j;
        }

        return res; // 返回最大水量
    }
};

Python 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution:
  def maxArea(self, height: List[int]) -> int:
    i, j = 0, len(height) - 1
    res = 0
    while i < j:
      res = max(res, min(height[i], height[j]) * (j - i));
      if height[i] < height[j]:
        i += 1
      else:
        j -= 1
    return res

Go 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


func maxArea(height []int) int {
  i, j := 0, len(height) - 1
  res := 0
  for i < j {
    h := 0
    if height[i] < height[j] {
      h = height[i]
    } else {
      h = height[j]
    }

    area := h * (j - i)
    if area > res {
      res = area
    }

    if height[i] < height[j] {
      i ++
    } else {
      j --
    }
  }
  return res
}

JavaScript 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function (height) {
  let i = 0,
    j = height.length - 1;
  let res = 0;

  while (i < j) {
    res = Math.max(res, Math.min(height[i], height[j]) * (j - i));
    if (height[i] < height[j]) {
      i++;
    } else {
      j--;
    }
  }
  return res;
};