盛最多水的容器

题解思路

本题的目标是找到两条竖线，使得它们与x轴形成的容器能容纳最多的水。水的容量由 较短的竖线高度 和 两条竖线的横坐标距离 决定，即：

$\text{容积}$$= \min(\text{height}[left], \text{height}$$[right]) \times (\text{right} - \text{left})$

最直观的解法是 暴力枚举 两条竖线的所有可能组合，但时间复杂度为 $O(n^2)$，会超时。

双指针优化

Leetcode 5.盛最多水的容器-原题链接

题目内容

给定一个长度为$n$的整数数组$height$ 。有 $n$ 条垂线，第 $i$ 条线的两个端点是 $(i, 0)$ 和 $(i, height[i])$ 。

找出其中的两条线，使得它们与 $x$轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明: 你不能倾斜容器。

输入描述

输出描述

样例1

输入

9
1 8 6 2 5 4 8 3 7

输出

49

说明

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

样例2

输入

2
1 1

输出

1

提示

• $n == height.length$
• $2 <= n <= 10^5$
• $0 <= height[i] <= 10^4$