Leetcode
2024 年 7 月 29 日
[Leetcode] 力扣 热题100道--双指针2: 11. 盛最多水的容器(中等)
给定一个长度为 n 的整数数组。有 n 条垂线, 第 i 条线的两个端点是 (i, 0) 和 (i, height[i]). 找出其中的两条线, 使得它们与 x 轴共同构成的容器可以容纳最多的水。
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;
}
};
版权声明：自由转载-非商用-非衍生-保持署名（创意共享3.0许可证）
作者： 哈米d1ch 发表日期：2024 年 7 月 29 日