「LeetCode Hot 100 」移动零 & 盛最多水的容器
0. 前言
LeetCode Hot 100 几乎是每位冲刺互联网大厂的同学都会接触到的经典题单,其重要性不言而喻。
本系列主要记录我的刷题过程,包括解题思路、代码实现以及学习中的思考与总结。
既是写给自己复习的笔记,也希望能给同样在刷题的你提供一些参考。
本期的主题是「双指针」,题目如下:
- 283. 移动零(简单)
- 11. 盛最多水的容器(中等)
1. 移动零
1. 题目描述
题目: 283. 移动零
难度: 简单
给定一个整数数组 nums,将所有的 0 移动到数组末尾,同时保持非零元素的相对顺序不变。
注意:必须在原数组上进行操作,不能复制数组。
示例 1:
▼text复制代码输入:nums = [0, 1, 0, 3, 12] 输出:[1, 3, 12, 0, 0]
示例 2:
▼text复制代码输入:nums = [0] 输出:[0]
2. 解题思路
一个整数数组 nums,要求是将所有的 0 移动到数组末尾,且保持非零元素的相对顺序不变
先看「保持非零元素的相对顺序不变」,这意味着我们不能直接按照数值大小进行排序,否则可能打乱非零元素原本的相对顺序。
接着看「将所有的 0 移动到数组末尾」,那么数组元素就被分为了两类,一类是零,一类是非零
如果我们要将零移动到数组末尾,那么这个数组的末尾是从哪里开始的呢?是由非零元素的个数决定的,那我们去获取非零元素的个数简单吗?是可以通过遍历数组,然后统计个数来实现的,但有没有更简单的方法呢?
不是分为了两类嘛,我们把零放到后面比较麻烦,是不是可以考虑把非零放在前面呢?
这也就引申出了这道题的思路,遍历数组,采用双指针,一个负责遍历数组,一个负责记录下一个非零元素应该放置的位置,当遇到非零元素时,将其放到对应的位置即可
3. 代码实现
▼python复制代码# left 指向下一个应该存放非零元素的位置 left = 0 # right 遍历列表,寻找非零元素 for right in range(len(nums)): # 找到非零元素,将其交换到前面 if nums[right] != 0: nums[left], nums[right] = nums[right], nums[left] # 更新下一个非零元素应该存放的位置 left += 1
这里使用的是 Python 的多重赋值语法:
▼text复制代码a, b = b, a
它可以在一行代码中交换两个变量的值。
需要注意,这道题要求原地修改列表,因此不需要返回新的列表。
4. 复杂度分析
1. 时间复杂度
核心问题:随着输入规模增大,算法的计算工作量如何增长?
这个算法当中的 n 就是列表 nums 的元素个数
for 循环内操作的时间复杂度都是 O(1),循环最多执行 n 次,那么这个算法的时间复杂度就是 O(n)
2. 空间复杂度
核心问题:随着输入规模增大,算法额外需要同时占用的存储空间如何增长?
空间复杂度考虑的是算法 额外 所占用的存储空间如何增长
在这算法当中会发现是没有创建额外容器的,两个指针的空间开销也是 O(1) 级别,所以其空间复杂度就是 O(1)
2. 盛最多水的容器
1. 题目描述
题目: 11. 盛最多水的容器
难度: 中等
给定一个长度为 n 的整数数组 height,数组中的每个元素代表对应位置竖线的高度。
从中选择两条竖线,使它们与 x 轴共同组成一个容器,并让容器能够容纳的水量最大。
返回这个容器能够容纳的最大水量。
注意:容器不能倾斜。

示例 1:
▼text复制代码输入:height = [1, 8, 6, 2, 5, 4, 8, 3, 7] 输出:49
示例 2:
▼text复制代码输入:height = [1, 1] 输出:1
2. 解题思路
这道题是需要返回这个容器能够容纳的最大水量,那么这个最大水量如何来计算的呢?
很简单呀,两端 x轴下标做差 * 两端较低的那个竖线的高度
对应成公式的话,就是
▼python复制代码# right - left 是两条竖线之间的宽度 # min(height[left],height[right]) 是两条竖线当中较短的那条的高度 (right - left) * min(height[left],height[right])
公式我们已经确定了,接下来就是要思考如何变化才能找到更大的水量
我们假设左右两条竖线分别如下:

如果我们保持左边高度为 3 的竖线不变,只移动右边的话,可以确定的事实是 right - left 宽度是一定会变小的;且高度最高依然不会超过 3,那么根据水量计算的公式来看,是一定不会比当前更大的
因此,保留较短的竖线、移动较长的竖线,不可能找到更优的结果。
3. 代码实现
▼python复制代码# 记录最大面积 max_area = 0 # 左右指针分别位于列表两端 left = 0 right = len(height) - 1 while left < right: # 计算当前容器的面积 current_area = (right - left) * min(height[left], height[right]) # 更新历史最大面积 if current_area > max_area: max_area = current_area # 移动较短的那条线 if height[left] > height[right]: right -= 1 else: left += 1 return max_area
4. 复杂度分析
1. 时间复杂度
核心问题:随着输入规模增大,算法的计算工作量如何增长?
在这个算法当中的 n 就是 height 的元素个数
while 循环的话,最多会执行 (n-1) 次
循环内操作的时间复杂度都是 O(1)
那么该算法的时间复杂度也就是 O(n)
2. 空间复杂度
核心问题:随着输入规模增大,算法额外需要同时占用的存储空间如何增长?
该算法当中没有额外的容器,变量的话,left、right 两个指针、current_area、max_area 也都不会随着输入规模的增长而发生增长,故该算法的空间复杂度是 O(1)
3. 总结
1. 两道题中,双指针分别承担什么角色?
| 对比 | 移动零 | 盛最多水的容器 |
|---|---|---|
| 初始位置 | 两个指针都从左侧开始 | 分别从数组两端开始 |
| 指针职责 | right 寻找非零元素,left 记录放置位置 | left 和 right 共同确定当前容器 |
| 移动方式 | 同向移动 | 相向移动 |
| 移动条件 | right 每轮前进,left 遇到非零元素才前进 | 每轮移动较短竖线对应的指针 |
2. 最值得记住的是什么?
我倒是没有想出什么万能的「双指针解题公式」,但可以就这两道题,记住两个思路:
移动零:
当直接处理目标元素比较麻烦时,是否可以反过来处理另一类元素?
盛最多水的容器:
当需要寻找最优结果时,能否根据当前条件,排除那些不可能产生更优结果的选择?
平台同名:花萍雨呀,将硬核的知识通俗化,更多有趣的专栏待你解锁~
如果这篇文章对你有用,记得一键三连再走哦!
我们下期见!
