type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给定一个长度为
n 的整数数组 height 。有
n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线,使得它们与
x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。
示例 1:

示例 2:
提示:
n == height.length
2 <= n <= 105
0 <= height[i] <= 104
解法:双指针
把每条垂线当成一堵墙,左右两墙围出一个“水槽”。水量=短板高度 × 宽度 (
area = (r-l) * min(h[l], h[r]))。- 初始: 左右指针
l=0, r=n-1
- 移动指针规则:
- 如果 height[l] < height[r] ,移动左指针 l += 1 。
- 否则,移动右指针 r −= 1。
为了尝试获得更大的面积,必须增加容器的高 或者宽。
宽度每次向内收缩,必定减少;因此想要增大面积,只有尝试找到更高的短板。
复杂度
- 时间:
O(n)(两指针各走一次)
- 空间:
O(1)
- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode-11-盛最多水的容器
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。
上一篇
[Leetcode 5] 最长回文子串
下一篇
[Leetcode 14] 最长公共前缀