盛最多水的容器

发表于 | 阅读次数: |

题目
给定 n 个非负整数 a1,a2, … ,an，每个数代表坐标中间的一个点 (i, ai)；在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)；找出其中的两条线，使它们与 x 轴共同构成的容器能容纳的水最多。

示例

1
2
输入：[1,8,6,2,5,4,8,3,7]
输出：49

解答

  • 方法一：最简单也是最复杂的方法，简单是处理逻辑简单，复杂时运算量比较大；将数组中的每个数字分别循环，将其与后面的各个值进行面积计算，并取出其中构成容器的最大值。

CODE

1
2
3
4
5
6
7
8
9
10
11
function maxArea(data) {
  let maxNum = 0;

  for (let i = 0; i < data.length - 1; i++) {
    for (let j = i + 1; j < data.length; j++) {
      maxNum = Math.max(maxNum, (j - i) * Math.min(data[i], data[j]));
    }
  }

  return maxNum;
}

时间复杂度：O(n2)，循环了两次
空间复杂度：O(1)，使用的一个恒定空间

  • 方法二：双指针法，即两段线之间的区域面积总是受最短的那一条所限制，因此可以将两个指针分别放在头部和尾部，另外使用一个 maxArea 来存储最大面积，在移动每一步首尾的指针时都会计算面积并进行更新 maxArea，更新后将较短的指针长度向较长的一端移动一步；最终，在两个指针到达同一个位置后停止。

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function maxAreaHandler(data) {
  let maxNum = 0,
      lIndex = 0,
      rIndex = data.length - 1;

  while (lIndex < rIndex) {
    maxNum = Math.max(maxNum, (rIndex - lIndex) * Math.min(data[lIndex], data[rIndex]));

    if (data[lIndex] <= data[rIndex]) {
      lIndex++;
    } else {
      rIndex++;
    }
  }

  return maxNum;
}

时间复杂度：O(n)，只是循环了一次
空间复杂度：O(1)

总结
在计算盛最多水的容器算法中，最主要的就是计算最大值；要么从头开始依次进行计算比较，要么从两端向中间共同循环，因此就产生了不同的时间复杂度。