LeetCode11-盛最多水的容器

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/container-with-most-water/

中文链接：https://leetcode-cn.com/problems/container-with-most-water/

题目详述

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

说明：你不能倾斜容器，且 n 的值至少为 2。

img

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例:

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

题目详解

题目转化一下，实际上就是垂直的两条线段将会与坐标轴构成一个矩形区域，较短线段的长度将会作为矩形区域的宽度，两线间距将会作为矩形区域的长度，最大化该矩形区域的面积。

方法一：直接枚举每对可能出现的线段组合并找出这些情况之下的最大面积。时间复杂度为 O(n^2)。

方法二：运用双指针，时间复杂度为 O(n)。

  • 思路：两线段之间形成的区域总是会受到其中较短那条长度的限制。并且，两线段距离越远，得到的面积就越大。
  • 使用双指针，一个放在开头，一个置于末尾。
  • 在遍历过程中，计算指针所指向的两条线段形成的区域面积并更新最大面积。
  • 将指向较短线段的指针向较长线段那端移动。
  • 若两条线段长度相等，则任意移动二者之一即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class LeetCode_00011 {

    public int maxArea(int[] height) {
        int i = 0;
        int j = height.length - 1;
        int res = 0;
        while (i < j) {
            int area = (j - i) * Math.min(height[i], height[j]);
            res = Math.max(res, area);
            if (height[i] < height[j]) {
                ++i;
            } else {
                --j;
            }
        }
        return res;
    }
}