加餐与答疑 | 第一期 ：一问一答

数据结构与算法面试宝典 - 前微软资深软件工程师 - 拉勾教育

《数据结构与算法面试宝典》专栏于 2021 年 3 月 1 日在拉勾教育上线。

看着专栏的订阅数直线上升，我既兴奋又忐忑。兴奋的是，积累数年、打磨半年之久的 “算法面试” 终于和大家见面了。忐忑的是担心词不达意，表达不严谨的地方，让大家花更多的时间来消化。

这两天，我在处理留言的时候，关注到有几位同学对例题 4 这道题目有些疑问，因此我想借着这篇 “加餐” 的机会，挑选一些留言，拿出来分析一下。以下是我摘选的部分留言：

仔细看过你们的提问后，我认为例 4 的题意在表述上不够严谨，所以在内容上做了一些优化和调整。以下是优化前后的题目对比：

【分析】题目优化后，我们再次强调了 “字典序” 这一概念，并给出字典序的说明。优化前题目中没有明确告知 “字典序最小”，所以才会导致大家对这道题目产生了疑问。

在这里，我也为以上不严谨的表述向你表示歉意。

除去订正题意以外，我们再一起看看其他同学提出的一些有趣的问题，搂草打兔子，万一你也有这些疑问，那就一起解决了。

有趣的 Q & A

例题 3：找出数组中右边比我小的元素

【题目】一个整数数组 A，找到每个元素：右边第一个比我小的下标位置，没有则用 -1 表示。

输入：[5, 2]

输出：[1, -1]

解释：因为元素 5 的右边离我最近且比我小的位置应该是 A[1]，最后一个元素 2 右边没有比 2 小的元素，所以应该输出 -1。

接口：int[] findRightSmall(int[] A);

关于这道题，我从留言中摘选的问题如下：

【小结】在面试中，写代码时一定要注意边界验证。接下来我们看一下关于题意的交流。

例题 2：大鱼吃小鱼

【题目】在水中有许多鱼，可以认为这些鱼停放在 x 轴上。再给定两个数组 Size，Dir，Size[i] 表示第 i 条鱼的大小，Dir[i] 表示鱼的方向 （0 表示向左游，1 表示向右游）。这两个数组分别表示鱼的大小和游动的方向，并且两个数组的长度相等。鱼的行为符合以下几个条件:

1. 所有的鱼都同时开始游动，每次按照鱼的方向，都游动一个单位距离；
2. 当方向相对时，大鱼会吃掉小鱼；
3. 鱼的大小都不一样。

输入：Size = [4, 2, 5, 3, 1], Dir = [1, 1, 0, 0, 0]

输出：3

请完成以下接口来计算还剩下几条鱼？

int solution(int[] Size, int[] Dir);

关于这道题，我从留言中摘选的问题如下：

【分析】首先要说明的是：

• 大鱼和小鱼只能在一条直线上游动（肯定和你平时玩的游戏不一样！）
• 此外，它们只能向左游，或者向右游。
• 并且所有的鱼的速度都一样。只是游动的方向不一样。
• 没有一样大的鱼。

我们来看一个简单的例子，用 > 表示向右游，< 表示向左游。接下来我们通过几个 Case 详细说明一下这情况。

Case 1： 假设有两条鱼，向着同样的方向游。比如，3>, 5> 一起向右游动。这个时候，大鱼是吃不了小鱼的。因为它们总是向一个方向游，并且速度一样，鱼也不能换方向。

Case 2： 假设有两条鱼，<3, 5>，这个时候大鱼仍然吃不了小鱼。因为它们是向相反方向游动的。

Case 3： 假设有两条鱼，3> <5，此时它们相向而游，大鱼一定会把小鱼吃掉。所以最后只会有 <5 留下来。

Case 4： 假设有 3 条鱼，3> 5> <4，首先碰面的是 5> <4, size = 5 的鱼会把 size = 4 的鱼吃掉。情况就退化成为 3> 5>。所以这种情况下，还会有 3> 5> 留下来，也就是还有两条鱼会留下来。

【小结】如果在面试中，没有听清楚面试官的问题，那么一定要提出自己的问题，最好是举个输入例子来表明自己哪里不清晰。

思考题：求出相邻的木板能剪出的最大矩形面积

【题目】给定一个数组，数组中的元素代表木板的高度。请你求出相邻木板能剪出的最大矩形面积。

关于这道题，我从留言中摘选的问题如下：

【小结】在阅读专栏的时候，难免会遇到各种各样的问题，及时的交流能够搬开学习过程中的障碍。

德鲁伊的叮嘱

其实专栏内容和面试场景是不太一样的。专栏写作应该是表述得越清晰越好，而面试提问则不需要遵循固定的原则。有时候面试官提出一个问题，会故意说得不清不楚，预设陷阱的情况在面试中时常存在。

做了多年面试官，结合我在实际工作中的切身体会，我再给你提几个醒，说说面试时应该问什么、不能问什么、提问的时长。

关于问什么

比如：请实现一棵树的层次遍历。

实际上这就是一个非常不清晰的问题。面试官的用意是希望候选人遇到模糊的问题时，能够主动识别出，然后有针对性地提出你的疑问，这也是在展现你的洞察力和沟通能力。

你可以向面试官提问，比如：

1. 什么样的树？是二叉树吗？还是多叉树？
2. 返回值是什么样的呢？
3. 树里面结点的值是整数吗？还是用字符串？

总之，在面试中，你拿到一道题，如果看得很明白，也尽量就一个 Case 和面试官做一下交流。如果你看不明白，有点迷糊，那么更需要通过和面试官交流把题意弄清楚。你可以主动去问清楚需求，而不是毫无思考就开始干活。给面试官传达，你在实际工作中具备挖掘和理解客户需求的能力。

关于不能问什么

有的问题是不适合在澄清题意的时候问的，尤其是套答案式的提问（不要抖机灵）。比如：

1. 这个是用二分搜索吗？
2. 具体算法的操作步骤是这样吗？

关于问多久？

提问时间不宜太长。一般就问题本身的交流大概会在 2~3 分钟以内，除非遇到了特别长的面试题。

德鲁伊说

我在写作专栏时，对一些内容的描述可能不够准确，非常感谢你们及时指出来！我认为，这也是技术人应有的态度，请你不要迟疑提出疑问，也不要吝啬表达自己的观点。借着这个机会，也是我学习和思考如何将课程更加清晰地呈现给你，也让我们一起把算法面试前的准备做得更充分！

作者与读者的思考路径不同，多一些不一样角度的碰撞，可能会产生意想不到的价值。当然，也可能诞生一篇加餐内容。：）