描述

题目描述

首先给定我们一个数组，我们要找到可以盛水的最大值，然后这个就是取决于两块板子长度之间最短的那个，然后我们再乘上他们之间的距离，就是我们可以呈的水了

样例解释

[1,7,3,2,4,5,8,2,7]

这里给我们的是每一个位置的板子的一个长度，然后我们现在可以发现，其实我们选择 $7$ 和 $7$ 这两块板子组成的水是最多的，这个我们可以想一下，他们的距离更长，然后长度也长

所以我们的输出是

7 * 7 * (8 - 1) == 49

题解

解法一：暴力出奇迹（会TLE）

解题思路

首先我们可以简单的想一下，我们最简单的一个思路，我们应该是如何去找到这个最大的值，我们是不是可以这样子，我们从0开始对每一位进行往后寻找，每次更新我们的一个最大值

代码实现

class Solution {
public:
    int maxArea(vector<int>& height) {
        int len = height.size(), maxx = 0; 
//         获取数组长度，开始设置最大值为0
        for (int i = 0; i < len; i++) {
//             遍历每一个起点
            for (int j = i + 1; j < len; j++) {
//             从每一个起点的后一个点去寻找最大值
                maxx = max(maxx, min(height[i], height[j]) * (j - i));
//                 这里我们每次更新最大值，一个是我们矩形的面积一个是我们的最大值
            }
        }
        return maxx;
//         返回我们的最大值
    }
};

时空复杂度

时间复杂度： $O (n^{2})$

理由如下：我们进行了两层循环时间复杂度是数组长度的平方，如果数组长度为n，则我们的时间复杂度就是 $(n^{2})$

空间复杂度： $O (1)$

理由如下：我们未引入新的变量空间，所以我们的空间复杂度是 $O (1)$

需要注意！！！

这里我们的这个做法是最为朴素的一个做法，它实际上是会超时的，因为我们 $n$ 的极限情况是会取到 $1 e 5$ ，然后我们的时间会达到 $1 e 10$ ，我们可以知道C++一般一秒是可以运行 $3 e 8$ 左右的数据，所以我们是会超时的，那我们如何优化，就引出来了我们的解法二

解法二：双指针（尺取法）

解题思路

我们发现我们直接朴素的暴力两重循环会超时，那我们想一下是不是有什么优化可以做一下，我们发现我们可以是不是得到这么一个公式

总存水量 = 两个板子之间的最小值 * 两个板子之间的距离

那么我们是不是可以，用两个指针，一个指向开头，一个指向结尾，然后我们每次移动一个指针，这时候我们要考虑一个问题，我们要移动哪一个指针，我们看到这个公式，我们可以思考一下，我们每次移动指针，两个板子之间的距离都是会变小，那么我们要是尽可能的想让我们总存水量变大，那么我们就要让我们两个板子之间的最小值变大，我们移动大的那个指针只会让我们的答案不变或者变小，所以我们只有移动小的那个指针才可以达到变化的一个作用

代码实现

class Solution {
public:
    int maxArea(vector<int>& height) {
        int len = height.size(), l = 0, r = len - 1, maxx = 0;
//         获取数组长度，左右指针分别指向开头和结尾，把最大值初始为0
        while(l < r) {
//             执行循环
            maxx = max(maxx, min(height[l], height[r]) * (r - l));
//             每次对最大值进行一个更新
            height[l] < height[r] ? l += 1 : r -= 1;
//             每次我们把数组值小的那边的指针移动
        }
        return maxx;
    }
};