hot100 11盛最多水的容器

题目描述

给定一个长度为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

思路

看评论里的一句话简直茅塞顿开

简单来说就是短边的下标向内移动，若移动长边则面积必定减少。

int maxArea(std::vector<int>& height) { int left = 0; int right = height.size() - 1; int max_area = 0; while (left < right) { int area = (right-left)*std::min(height[left], height[right]); max_area = std::max(max_area, area); if (height[left] < height[right]) { left++; // 左端长度更短 } else { right--; // 右端长度更短 } } return max_area; }

复杂度分析

• 时间复杂度：O(N)，双指针总计最多遍历整个数组一次。

• 空间复杂度：O(1)，只需要额外的常数级别的空间。