力扣——盛最多水的容器

题目描述：

给定一个长度为 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 <= 1e5
• 0 <= height[i] <= 1e4

---

一开始看这道题的时候，以为是动态规划，没想到是贪心！所以，求解本题的关键是，找到贪心的方法。

方法：当我们寻找最大容量时，可以从两边开始，然后向中间靠（我们知道，容器的体积取决于短边的长度），向中间靠意味着长方形的宽一定会变小（把容器的侧截面看作是长方形）

1、如果是长边向内，如果下一条是更长边，那对整个容器的长不起作用，因为容器的体积取决于短边，但是宽变小，所以此时容器的体积一定变小；如果下一条是更短边，那整个容器的短边就更短，并且宽变小，则整个容器的体积就会更小。所以长边向内，容器体积一定会变小；

2、如果是短边向内，如果下一条是更长边，那此时容器的短边就会更新，变成min（原来的长边，此时的新长边），但是向中间靠会使长方形的宽变小，但是长变大了，所以整个容器可能会变大，但是这就给我们提供了贪心的机会，有机会变大；如果下一条是更短边，那容器的体积就一定会变小；

综上所述，只有当短边向内的时候，容器的体积才有变大的可能性，所以我们设立两个指针，每次判断哪边是短边，然后一步一步向内靠拢即可；

---

AC代码：

class Solution {
public:
    int maxArea(vector<int>& height) 
    {
        int len = 0;
        len = height.size();
        int i=0, j=len-1;//i左指针，j右指针
        int v=0;//容量
        int _min =0;
        while(i<j)
        {
            _min = height[i] < height[j] ? height[i] : height[j];
            v = v > _min * (j - i) ? v : _min * (j - i);
            if(height[i]<height[j])i++;
            else j--;
        }
        return v;
    }
};

可能大家还有几点疑惑：

1、我们能不能从中间向两边扩展，这样不是更容易使容器的体积变大吗？当从中间向两边扩展时，那长方形的宽一定变大，则体积的大小完全取决于两边中的更短边，跟上面一样分析；

如果是长边向外，如果下一条是更长边，那对整个容器的长也不起作用，但宽变大，所以容器的体积一定变大；如果下一条是更短边，那整个容器的短边就更短，但宽变大，所以此时并不能判断容器体积变大还是变小；

如果是短边向外，如果下一条是更长边，那此时容器的短边就会更新，变成min（原来的长边，此时的新长边），宽变大，长也变大了，所以容器一定会变大；如果下一条是更短边，但宽变大，所以此时并不能判断容器体积变大还是变小；

综上可知，此时无论是移动长边还是短边，都是可能让容器体积变大或变小，所以这种方法不行。

2、另一个知识点是C++的三木运算符： condition ? expression1 : expression2；这个很简单

举个例子：z = x > y ? x : y ，意思是判断x和y谁更大，如果x更大，则x>y成立，把x赋值给z，否则z=y；

希望能帮助到大家！谢谢~