【力扣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.简单来说就是双指针一左一右那个矮就让哪个指针向另一边移动。个人认为这样的思路来源于距离xx越大面积很可能就越大。所以就先从x最大的左右两边开始计算然后逐步缩小移动更矮的那边寻找最优解。看来以后还是尽量不点提示了这个还是太直白了...三、题解class Solution { private: int max_water0; public: void twoPoints(vectorint height,int left,int right){ if(leftright){ return; } max_watermax(max_water,(right-left)*min(height[right],height[left])); if(height[left]height[right]){ twoPoints(height,left1,right); } else twoPoints(height,left,right-1); } int maxArea(vectorint height) { twoPoints(height,0,height.size()-1); return max_water; } };