「LeetCode Hot 100 」移动零 & 盛最多水的容器

0. 前言

LeetCode Hot 100 几乎是每位冲刺互联网大厂的同学都会接触到的经典题单,其重要性不言而喻。

本系列主要记录我的刷题过程,包括解题思路、代码实现以及学习中的思考与总结。

既是写给自己复习的笔记,也希望能给同样在刷题的你提供一些参考。

本期的主题是「双指针」,题目如下:

  1. 283. 移动零(简单)
  2. 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 轴共同组成一个容器,并让容器能够容纳的水量最大。

返回这个容器能够容纳的最大水量。

注意:容器不能倾斜。

image.png

示例 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])

公式我们已经确定了,接下来就是要思考如何变化才能找到更大的水量

我们假设左右两条竖线分别如下:

image.png

如果我们保持左边高度为 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. 最值得记住的是什么?

我倒是没有想出什么万能的「双指针解题公式」,但可以就这两道题,记住两个思路:

移动零:

当直接处理目标元素比较麻烦时,是否可以反过来处理另一类元素?

盛最多水的容器:

当需要寻找最优结果时,能否根据当前条件,排除那些不可能产生更优结果的选择?


  • 平台同名:花萍雨呀,将硬核的知识通俗化,更多有趣的专栏待你解锁~

  • 如果这篇文章对你有用,记得一键三连再走哦!

  • 我们下期见!

0个评论
点击登录,快来和大家讨论吧~
表情
图片
暂无评论
下载 APP