leetcode（双指针）11.盛最多水的容器（C++详细解释）DAY9

1.题目

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

**说明：**你不能倾斜容器。

示例

提示

2.解答思路

两层for循环的做法时间会超时
因此利用双指针进行一遍遍历。

我们要清楚：
每轮向内移动短板，所有消去的状态都 不会导致面积最大值丢失
即：向内移动短板的操作是为了

• 丢弃不可能的情况（裁剪无效搜索空间），
• 保留可能的情况（保留有效搜索空间），
• 然后对所有可能的情况枚举计算（在有效搜索空间中枚举搜索）即可得出结果。

3.实现代码

class Solution {
   
public:
    int maxArea(vector<int>& height) {
   
        int max = 0;//最后结果
        int i = 0, j = height.size()-1;
        int sum = 0; // 临时存放储水量

    while (i < j)
    {
   
        int a = height[i], b = height[j];
        sum = (j - i) * (b > a ? a : b);//计算当下的储水量
        
        /*若height[i]<height[j]时，
        增加i.  反之，减小j
        这个条件一定弄明白，这是关键。
         */
        if (a < b)//逐渐缩小比较范围
        {
   
            i++;
        }
        else
        {
   
            j--;
        }
        max = (sum > max ? sum : max);
    }

        return max;
    }
};

结果

4.总结

双指针的变化条件要找准。

双指针的一遍遍历 比 两层for循环的暴力解法快很多。

感冒好了不少了，课本的题正在做，这几天估计就会有更新啦

自信，坚持，upup～