LeetCode 11.盛最多水的容器

11.盛最多水的容器

题面：

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

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

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

说明：你不能倾斜容器。

示例：（建议参考原题面）
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：(8, 7)情况下，容器能够容纳水的最大值为 49。

解析：

• 对于这道题目，暴力就是两层循环，遍历所有的左右栏杆的情况，求解出其中的最大值。
• 优化：我们可以进行的优化就是在答案的搜索空间内减少不必要的遍历验证。
• 双指针的思想：它先令底边(right - left)最大，这样我们接下来的任何遍历操作都会使得底边变小。设当前我们遍历至step[i]，此时的面积为min(height[left], height[right]) * (right - left)，对于step[i+1]而言，我们可以进行的操作就是右移左边的栏杆(left++)与左移右边的栏杆(right--)。此时不论移动哪一边，底边都是变小，不妨设height[left] < height[right]，ans = height[left] * (right - left)，如果我们移动长的栏杆，会出现下面两种情况：

\[\begin{flalign} &case_1：height[--right] < height[left] \rightarrow area = height[--right] * (right - left - 1) \rightarrow area < ans\\ &case_2：height[--right] ≥ height[left] \rightarrow area = height[left] * (right - left - 1) \rightarrow area < ans& \end{flalign} \]

• 此后我们会发现，移动长的一条边的话，我们的搜索就是无意义的了，我们在以当前的面积为上界进行搜索，但是如果我们移动较短的一条边，就会有如下三种情况：

\[\begin{flalign} &case_1：height[++left] > height[right] \rightarrow area = height[right] * (right - left - 1) \rightarrow area ? ans\\ &case_2：height[++left] = height[right] \rightarrow area = height[right] * (right - left - 1) \rightarrow area ? ans\\ &case_3：height[++left] < height[right] \rightarrow area = height[++left] * (right - left - 1) \rightarrow area ? ans& \end{flalign} \]

• 此时我们可以发现，针对于移动较短的一边而言，此时可能存在比当前面积更大的情况，此时的搜索才是有意义的，而对于这道题目而言，就是基于这样实现的双指针，减少了很多无意义的搜索，将\(O(n ^ 2)\)的搜索空间使用\(O(n)\)的时间复杂度完成最大面积的搜索。

复杂度

时间复杂度\(O(n)\)
空间复杂度\(O(1)\)

Code

// C++
class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0;
        int right = height.size() - 1;
        int ans = min(height[left], height[right]) * (right - left);
        while (left < right)
        {
            if (height[left] <= height[right])
            {
                left++;
            } else
            {
                right--;
            }
            int temp = min(height[left], height[right]) * (right - left);
            ans = max(ans, temp);
        }
        return ans;
    }
};

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

// Rust
use std::cmp;

impl Solution {
    pub fn max_area(height: Vec<i32>) -> i32 {
        let mut left = 0;
        let mut right = height.len() - 1;
        let mut ans = cmp::min(height[left], height[right]) * (right - left) as i32;
        while left < right
        {
            if height[left] <= height[right]
            {
                left += 1;
            } else {
                right -= 1;
            }
            let temp = cmp::min(height[left], height[right]) * (right - left) as i32;
            ans = cmp::max(ans, temp);
        }
        ans
    }
}