LeetCode 11. 盛最多水的容器

给定一个长度为n的整数数组height。有n条垂线第i条线的两个端点是(i, 0)和(i, height[i])。找出其中的两条线使得它们与x轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。说明你不能倾斜容器。思路:容器能装多少水,取决于两件事:两条线的距离(宽)和较矮的那条线(高)。面积 宽 × 矮边。最直接的想法:枚举所有 (i, j) 组合,算出每个面积取最大。暴力解法(逻辑正确,但会超时):class Solution { public: int maxArea(vectorint height) { int nheight.size(); int ans0; for(int i0;in-1;i) { for(int ji1;jn;j) { ansmax(ans,(j-i)*min(height[i],height[j])); } } return ans; } };怎么优化(双指针):从最宽的开始——左右指针放在两端。每步比较两条边,只移动较矮的那一边:因为移动高的一边,宽度变小、高度仍由矮边决定,面积只会更小,白移动;只有移动矮的一边,才可能遇到更高的边,面积才有机会变大。规则一句话:谁矮移动谁。class Solution { public: int maxArea(vectorint height) { int nheight.size(); int left0; int rightn-1; int ans0; while(leftright) { ansmax(ans,(right-left)*min(height[left],height[right])); if(height[left]height[right]) { left; } else { right--; } } return ans; } };