盛最多水的容器

发表于
本文字数： 780 阅读时长 ≈ 1 分钟

LeetCode题目，11. Container With Most Water

先看题目描述

大意就是给定一个数组代表 n 条垂线的高度，让我们找出两条垂线，使其与 x 轴组成的容器可盛水的容积最大，让我们将其最大容积返回

算法和思路

双指针法

算法流程：

  • 定义两条指针 i 和 j，初始化 i = 0，j = n - 1，再维护一个 max = 0 来记录最大容积
  • 初始时 i 和 j 指针指向数组左右两端，此时的容纳水量为 min(i, j) * (j - i)
  • 此时我们需要向内移动指针，如果我们移动数字较大的那个指针，那么前者「两个指针指向的数字中较小值」不会增加，后者「指针之间的距离」会减小，那么这个乘积会减小。因此，我们移动数字较大的那个指针是不合理的。因此，我们向内移动 数字较小的那个指针
  • 移动指针后计算新的可容纳水量并更新 max 值
  • 重复上述过程直至 i，j 指针相遇
  • 最后返回 max 值即可

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int maxArea(int[] height) {
        int len = height.length;
        int i = 0;
        int j = len - 1;
        int max = 0;
        while (i < j) {
            max = height[i] < height[j] ? Math.max(max, (j - i) * height[i++]) : Math.max(max, (j - i) * height[j--]);
        }
        return max;
    }
}