11. 盛最多水的容器

Origin: LeetCode 11

题目描述

给定一个长度为 n 的整数数组 height，每个数表示坐标轴上竖线的高度。两条竖线和 x 轴围成的区域可以盛水，找出能盛最多水的两条线。返回最大面积。

示例

Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7] Output: 49

Explanation: 第 1 条线（高 8）和第 8 条线（高 7）围成的区域：min(8,7) × 7 = 49

Input: height = [1, 1] Output: 1

约束

• 2 <= height.length <= 10
• 0 <= height[i] <= 10

关键信息

• 面积 = min(height[left], height[right]) × (right - left)
• 双指针从两端向中间收缩
• 每次移动较矮的那一边（移动高的不可能让面积变大）

Resolution

我的解法

function maxArea(height: number[]): number {
    let left = 0
    let right = height.length - 1
    let area = 0
    while (left < right) {
        const curAara = Math.min(height[left], height[right]) * (right - left)
        if (height[left] > height[right]) {
            right--
        } else {
            left++
        }
        area = Math.max(area, curAara)
    }
    return area
}

解题思路

双指针从两端收缩。面积 = min(height[left], height[right]) × (right - left)。每次移动较矮的那一边：

• 移动高的：宽度变窄，高度还是被矮的限制，面积只会更小
• 移动矮的：宽度变窄，但高度可能变高，面积有可能变大

踩坑

• 宽度是 right - left 不是 right - left + 1（两条线之间的距离，不是元素个数）
• while (left <= right) 应该是 <，等于时 width = 0 没意义

复杂度

• 时间：O(n)
• 空间：O(1)