【力扣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

二、思路

想了半小时，一直往单调栈在想，可是无果。点了下提示，直接报答案了...

（提示：Try to use two-pointers. Set one pointer to the left and one to the right of the array. Always move the pointer that points to the lower line.）

简单来说就是，双指针，一左一右，那个矮就让哪个指针向另一边移动。

个人认为这样的思路，来源于距离x，x越大面积很可能就越大。所以就先从x最大的左右两边开始计算，然后逐步缩小，移动更矮的那边寻找最优解。

看来以后还是尽量不点提示了，这个还是太直白了...

三、题解

class Solution { private: int max_water=0; public: void twoPoints(vector<int>& height,int left,int right){ if(left>=right){ return; } max_water=max(max_water,(right-left)*min(height[right],height[left])); if(height[left]<=height[right]){ twoPoints(height,left+1,right); } else twoPoints(height,left,right-1); } int maxArea(vector<int>& height) { twoPoints(height,0,height.size()-1); return max_water; } };