11. 盛最多水的容器 Link to 11. 盛最多水的容器

题意分析 Link to 题意分析

根据题目描述 和 实例分析:

1. 给定一个数组, 数组中的数据可看作桶高, 两数据之间的距离可看作桶底
2. 相邻数据之间的距离看作1
3. 数组中数据位置不可改变
4. 桶的容水量直接按照 桶底*桶高 计算, 所以可以看作是一个长方形
5. 即使是长方形面积的计算方式, 也要遵循 按照较低桶边计算容水量的特点

思路分析 Link to 思路分析

这样的题, 最简单的思路就是: 暴力遍历, 针对每条数据, 都遍历其他数据并作计算, 最终的时间复杂度为O(N^2)

思路很简单, 实现方式也很简单, 但很大概率超时:

暴力解法不行, 那就要尝试新的解法

计算容水量, 桶底*桶高, 即 两桶高之间的距离*两桶高之间较小值

而要计算最大容水量, 可以使用两指针分别指向数组头尾的方式, 遍历数组进行计算, 毕竟当 数组头尾数据作为桶高时, 桶底最大

两指针分别指向数组的首尾, 还需要遍历数组, 那么就会发生指针向数组中间移动的情况, 此时要记得 当指针向对方靠拢时, 桶底会减小

所以, 本题思路就是:

1. 使用双指针分别指向数组头尾数据, 两数据表示两桶高
2. 根据桶高和两指针距离, 计算容水量, 并记录最大容水量
3. 对比 当前计算的容水量 和 已记录的最大容水量, 并更新最大容水量
4. 直到两指针相遇, 则最大容水量记录完毕

那么, 自然而然就会出现一个问题: 如何移动指针? 或者说 什么情况下移动指针?

可以随意的将两指针向对方靠拢吗? 显然不行.

那么, 随便找一组数据思考一下:

考虑一下, 此时应该如何移动指针? 为什么?

一定是 将begin向右移动一位. 但是为什么?

因为8 > 1吗? begin的下一位8是我们主管看到的, 8 > 1也是我们主观判断的. 计算机不行

计算机可以对比之后再移动, 但是如果遇到比较小的值就一直不动了吗? 如果之后有较大的值呢?

不能 对比下一位与当前值的大小 来作为指针移动的原因, 而是要对比当前两指针指向数值的大小

要移动begin和end中, 指向较小数据的指针, 不能移动指向较大数据的指针

要牢记一个特点: 桶的容水量要用较低桶高来计算

如果 移动指向较大数据的指针, 那么 之后的数据计算出来的容水量 对比当前一定是减小的, 因为 用于计算容水量的桶高的最大值已经不会再变大 了, 而 桶底是固定减小的

要想计算出更大的容水量, 就只有移动指向较小数据的指针, 才可能实现

因为, 移动指向较小数据的指针, 才有可能增加计算容水量时的桶高

所以, 要移动指向较小数据的指针

每移动一次, 计算容水量, 并尝试更新最大容水量

直到两指针相遇, 能计算出的最大容水量就可以被记录下

代码实现 Link to 代码实现

本题的代码实现, 较为简单, 重要的是思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int maxArea(vector<int>& height) {
        int ret = 0;
        int begin = 0, end = height.size() - 1;
        while (begin < end) {
            int width = end - begin;
            int tol = height[begin] > height[end] ? height[end] * width : height[begin] * width;
            if (ret < tol) 
                ret = tol;
            
            if (height[begin] < height[end])
                begin++;
            else 
                end--;
        }

        return ret;
    }
};