Leetcode 2024 年 7 月 29 日

[Leetcode] 力扣热题100道--双指针2: 11. 盛最多水的容器(中等)

给定一个长度为 n 的整数数组。有 n 条垂线, 第 i 条线的两个端点是 (i, 0) 和 (i, height[i]). 找出其中的两条线, 使得它们与 x 轴共同构成的容器可以容纳最多的水。

Leetcode 算法题约1107字 -- 阅读时间≈4分钟

11. 盛最多水的容器

题意分析

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

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

思路分析

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

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

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

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

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

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

所以, 本题思路就是:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

代码实现

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

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;
    }
};

作者：哈米d1ch 发表日期：2024 年 7 月 29 日

[Leetcode] 力扣 热题100道--双指针2: 11. 盛最多水的容器(中等)

11. 盛最多水的容器

题意分析

思路分析

代码实现

[Leetcode] 力扣热题100道--双指针2: 11. 盛最多水的容器(中等)