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.length2 n 1050 height[i] 104思路看评论里的一句话简直茅塞顿开简单来说就是短边的下标向内移动若移动长边则面积必定减少。int maxArea(std::vectorint 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)只需要额外的常数级别的空间。