Leetcode-盛最多水的容器

给定一个长度为 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
class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0;
        int right = static_cast<int>(height.size()) - 1;
        int max_area = 0;
        while (right > left) {
            auto width = right - left;
            auto depth = height[left] > height[right] ? height[right--] : height[left++];
            max_area = max(max_area, depth * width);
        }
        return max_area;
    }
};
  • 变量定义与初始化

函数内部首先定义了三个变量 leftrightmax_area,分别表示容器的左边界、右边界和当前最大面积。其中,leftright 的初始值分别为 0 和 height 向量的长度减 1,max_area 的初始值为 0。

  • 双指针法计算最大面积

接下来使用双指针法计算容器的最大面积。在循环中,首先计算当前容器的宽度 width,即右边界 right 减去左边界 left。然后计算当前容器的深度 depth,即左右两端高度的较小值,根据这个深度和宽度计算当前容器的面积 area

如果当前面积 area 大于最大面积 max_area,则更新最大面积为当前面积。接着,根据左右两端的高度大小关系移动指针。如果右端高度小于左端高度,则将右指针左移一位;否则将左指针右移一位。直到左指针和右指针相遇,循环结束。


已发布

分类

来自

标签:

评论

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注