28.盛最多水的容器

题目

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

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

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

说明：你不能倾斜容器。

示例 1:

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

示例 2:

• 输入：height = [1,1]
• 输出：1

提示:

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

思路

• 求出两个index1和index2，其中index < index2，使得min(height[index1], height[index2]) * (index2 - index1)最大
• 核心就是：优先移动短板指针，因为面积是由短板的高度决定。

在每个状态下，无论长板或短板向中间收窄一格，都会导致水槽 底边宽度 −1，会 变短:

• 若向内 移动更短的板 ，水槽的短板 min(h[i],h[j]) 可能变大，因此下个水槽的面积 可能增大 。
• 若向内 移动更长的板 ，水槽的短板 min(h[i],h[j]) 不变或变小，因此下个水槽的面积 一定变小 。

因此，初始化双指针分列水槽左右两端，循环每轮将短板向内移动一格，并更新面积最大值，直到两指针相遇时跳出；即可获得最大面积。

class Solution:
    def maxArea(self, height: List[int]) -> int:
        i, j, res = 0, len(height) - 1, 0
        while i < j:
            if height[i] < height[j]:
                res = max(res, height[i] * (j - i))
                i += 1
            else:
                res = max(res, height[j] * (j - i))
                j -= 1
        return res

class Solution {
    fun maxArea(height: IntArray): Int {
        var result = 0

        val size = height.size

        var leftIndex = 0
        var rightIndex = size - 1

        while (leftIndex < rightIndex) {
            result = max(result, min(height[leftIndex], height[rightIndex]) * (rightIndex - leftIndex))
            if (height[leftIndex] < height[rightIndex]) {
                leftIndex ++
            } else {
                rightIndex --
            }
        }
        return result
    }
}

复杂度分析:

• 时间复杂度 O(N) ： 双指针遍历一次底边宽度 N 。

• 空间复杂度 O(1) ： 变量 i , j , res 使用常数额外空间。

• 下一题

• 邮箱 ：charon.chui@gmail.com
• Good Luck!