11. 盛最多水的容器（C++）_最大容器 代码

题干：
https://leetcode.cn/problems/container-with-most-water/

• 暴力解法：（leetcode可能跑不出结果）

class Solution {
public:
    int maxArea(vector<int>& height) {
        int high{ 0 };//高
        int wide{ 0 };//宽
        int result{ 0 };
        
		//所有的两两组合
        for (int i = 0; i < height.size(); i++) {
            for (int j = i; j < height.size(); j++) {
                //计算i,j构成的容器容纳量（忽略他们之间的柱子）
                high = min(height[i],height[j]);
                wide = j - i;
                int x = high * wide;
                result = result > x ? result : x;
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

• 经典双指针

可行性分析：我们要证明双指针移动的过程中不会漏掉我们的正确答案组合。

前提：请在脑海里想象一个很长的数组，有两个下标分别为x,y，这两个下标组成的两条线就是盛最多水的容器。

双指针移动，假设我们第一次碰到了x,y中的一个，不妨就是x，那么我们要做的理想情况就是，接下来x指针不动，只能另一个指针一直左移，直到指向y。（如果x指针右移了，就错过了最大容器）

因为x,y所组成的两条线就是盛最多水的容器，所以y右侧的元素都小于x，因此y右侧的指针会一直左移直到指向y，符合我们的预期。（试想如果y右侧的元素存在大于等于x的，那么该元素和x构成的容器盛水必然多余x,y构成的容器，因为它的高度是x的高度，不小于x,y容器，宽度大于x,y容器）

class Solution {
public:
    int maxArea(vector<int>& height) {
        int high{ 0 };//高
        int wide{ 0 };//宽
        int result{ 0 };//保存最大容器结果

        int left{ 0 };//左指针
        int right{ static_cast<int>(height.size() - 1) };//右指针

        while (left < right) {
            high = min(height[left], height[right]);
            wide = right - left;
            int x = high * wide;
            result = result > x ? result : x;      

            if (height[left] < height[right]) {
                left++;
            }
            else {
                right--;
            }
        }

        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27