跳到主要内容

盛最多水的容器

题目描述​

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

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

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

说明： 你不能倾斜容器。

示例​

输入：height = [1,8,6,2,5,4,8,3,7]
输出：49

解题思路​

双指针

  1. 初始化两个指针 left 和 right 分别指向数组的左右两端
  2. 计算当前容器的面积，并更新最大面积
  3. 移动指针：每次移动高度较小的指针，因为移动高度较大的指针不会增加容器的面积
  4. 重复步骤 2 和 3，直到两个指针相遇

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

C++ 解法​

#include <vector>
#include <algorithm>

class Solution {
public:
    int maxArea(std::vector<int> &height)
    {
        int left = 0, right = height.size() - 1;
        int maxArea = 0;

        while (left < right) {
            int h = std::min(height[left], height[right]);
            int w = right - left;
            maxArea = std::max(maxArea, h * w);

            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return maxArea;
    }
};

LeetCode链接： 11. 盛最多水的容器