[Leetcode 11] 盛最多水的容器

type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给定一个长度为 n 的整数数组 height 。
有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
 
示例 1:
notion image
 
示例 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)
 
上一篇
[Leetcode 5] 最长回文子串
下一篇
[Leetcode 14] 最长公共前缀