刷题的疑惑

Question

bobo老师您好，不好意思，在这里想请教一个跟图没有太大关系的问题。身边没有啥人可以请教，选择了在这里提问。

我的疑惑是：（我的疑惑可以简单理解为：碰到了难的高级的先把它给吃透，还是先打好其他的基础再来学习难的？）

我现在刷树(递归)的题比较得心应手，自己能独立完成树的好多中等难度题。树的题目中会有一些可以应用图的知识的题，所以我就开始了这门图论的学习。

但是前两天和同事们一起刷题的过程中，接触到了单调栈。这个我没怎么见过，于是想先把单调栈给吃透。但是好多单调栈的对于我来说好难，看别人的题解都要理解个大半天的。我怀疑自己的刷题基础和刷题思维训练还不够致使我理解单调栈很费力。

那以我现有必要是继续死磕单调栈直到学透的好，还是先放下来，先学其他的，到时再回来学习呢？

PS: 我现在的基础是，差不多9个月前我认认真真的上完了您的算法与数据结构体系课，应该入门了。从差不多2021.8月就开始比较坚持的刷leetcode了，也刷了450题(但是刷到了300题也是看到了你的公众号才知道该怎么刷题…)。喜欢递归和树。这方面的题做得还不错，其他类的题，做得还不太行，因为开始做其他类型的时候不知道刷题的正确姿势和要领T.T。

Answer 1

liuyubobobo 2022-03-20 19:01:08

根据你的描述，我认为你的担心没有必要，你在一条正确的道路上。

说实话，如果你使用递归和树已经很熟练了，甚至达到了“喜欢”的程度（你的原话），在我看来，你的算法基础已经问题不大了。我个人认为对递归的透彻理解，近乎是计算机专业的每一个同学都需要迈的一道非常非常重要的坎儿，甚至我知道很多高级工程师都没有特别好的迈过这道坎儿（但是他们在特定领域也不需要对递归甚至是对算法有特别透彻地理解，尤其是重业务开发的场景。）一旦迈过了这道坎儿，近乎再看大多数代码的时候，从代码的逻辑架构的角度，已经不会有大的问题了，剩下的问题，在我看来，都是相对具体的 technique。

比如线段树，在我看来就是一个具体的 technique。你有可能理解了递归，但是不懂线段树，这没有关系，因为你只要理解清楚了线段树到底在存些什么，涉及的每一个变量，每一个操作，每一个函数的语义是什么，再加上你对递归的深入理解，你看线段树的代码，是非常非常自然的。但是，如果你不懂递归，你可能觉得你对线段树到底是怎么回事儿已经清楚了，可是一看代码，就晕了。而这，对于计算机专业来说，是非常非常致命的。

递归是一个非常非常重要的组织逻辑的方式。重要到近乎计算机专业根本离不开他。算法的几大思想：分治，回溯，动态规划，分支限界，甚至是暴力枚举里，都到处都是递归的影子；从结构的角度，重要的结构都是树形或者图形的，因为真实的世界鲜有那么简单的“线性结构”。文件结构是树；html 是树；一个队列看起来是线性吧？但是一旦加入一个优先级，就是树了（优先队列是一个堆）；哈希表看起来和树没关系吧？java 8 对哈希表的优化应用了红黑树；数据库看起来是一堆数据堆在一起吧，建一个索引，就是在这些数据的索引字段上，建了一棵树。

==========

这种“计算机思维”的学习和具体的 technique 的学习，其实是一个互相的过程。更准确的说，我们是通过一个一个 technique 的学习，在逐渐培养计算机思维。快排，归并排序，链表，二分查找，二分搜索树，线段树，等等等等，全都在用递归，通过对这一个一个具体的 technique 的学习，我们最终理解了递归。但这是否意味着我们已经掌握了所有使用递归的 technique？绝对不是。

一旦这样的“计算机思维”已经掌握了的话，剩下的事情，基本上就是去学习一个一个具体的 technique。但是，technique 有常见和不常见之分。在我看来，单调栈就是一个不常用（至少在算法面试中不常见，甚至可能见到的概率极低）的一个非常具体的 technique。相较而言，无向图的最短路径使用 BFS；或者使用哈希表记录数据供随时查询；或者二分搜索解；或者使用回溯枚举所有的排列或者组合“暴力”解；或者使用优先队列快速获得最大最小值，等等等等，都是更常见的 technique。

另一方面，technique 也是和领域相关。比如在编译原理中，可以使用两个栈做中缀表达式的解析，这被称为是 shunting-yard algorithm。（如果感兴趣可以参考这里：https://en.wikipedia.org/wiki/Shunting-yard_algorithm  ）那么是不是你学会了栈，就“自动”了解了这个算法？不是的。但是，你要想了解这个算法，必须懂什么是栈。

这就是“算法和数据结构”是计算机专业的基础的意思。同理，操作系统的任务调度需要优先队列（堆），编译原理中的文件依赖需要有向图；数据库中的索引是一棵 n 叉搜索树（B树）；图像学中用 8 叉树管理场景；等等等等，这些都是我们可以继续探究的各个领域解决问题的 technique。你不知道，很正常；但你学习了算法和数据结构以后，就具有了深入学习这些领域的专有算法的前提条件，不会摸不到头脑。

==========

单调栈和单调队列在算法竞赛中遇到的几率更高一些。但其实也主要是在动态规划的优化上使用。并且，在绝大多数情况下，单调栈和单调队列的作用可以被其他区间结构替换（比如线段树或者树状数组），只不过单调栈和单调队列能做到 O(n）而非 O(nlogn) 而已。但是，在大多数情况下，logn 的区别是不构成性能的“灾难”的。说实话，我没有特别听说过面试中有单调栈或者单调队列的问题。我坚信是因为 Leetcode 上的几个单调栈和单调队列的问题，让这个 technique 对于大多数程序员来说更加“流行”了。但说实话，如果真说 technique 的话，算法竞赛中常用的 technique 数量，近乎是面试问题常用 technique 的十倍以上应该不夸张。所以这种 technique 的学习近乎是无止境的。对于大多数工程师来说，没有必要因为不知道几个 technique 而沮丧。（相反，应该觉得很正常。）

如果你真的特别想理解单调栈是怎么回事儿，我推荐看这份题解：https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/bao-li-jie-fa-zhan-by-liweiwei1419/ 这是我见过的写的最清楚的模拟单调栈，通过模拟这个过程，可以让你理解为什么要这样做的题解。作者也是我的课程的一名学生：）

但是依然是，我要强调，单调栈和单调队列并不是非常重要的 technique，我认为其实你忽略它没有问题。但我觉得你的水平，自己研究上面那份题解，是能理解单调栈的。

同时，我也不认为这是你的基础或者思维有问题。恰恰相反，你的描述让我觉得你的基础或者思维非常好，甚至我能感受到你对自己的要求是非常高的，对什么叫“自己真正掌握了”的标准大概率是比一般人要严格的。所以虽然你觉得自己还不够好，但你的基础很有可能比很多所谓的“知道几个单调栈的问题，知道怎么解这些问题”的同学是要好的。

我建议你再给自己一个完整下午的时间，按照上面的题解，从这个 84 号问题开始，再静下心来仔细研究一下单调栈，看能不能搞明白。如果不能，就先不要搞了。先去搞其他更“常见”，“经典”或者有“代表性”的问题。

你的问题：碰到了难的高级的先把它给吃透，还是先打好其他的基础再来学习难的？

我的回答绝对是：基础。

什么叫基础？一个简单的标准是，至少大多数这个领域的“教科书”都会介绍这个东西。说实话，除了竞赛书籍，我就没见过哪本算法书讲过单调栈单调队列的。

Leetcode 很多问题有这个“毛病”，再比如 5 号问题题解中的 manacher 算法，或者 142 号问题中的 floyd 寻环算法。他的本意是好的，想拓展大家算法上的见识，但是却会让很多人误以为自己的基础很差，什么都不知道。但其实，这些算法在一般的教科书中都没有，他们是非常“专门”的 technique，不了解其实是很正常的。

继续加油！：）

• 提问者 努力做学霸123 #1

  受益很多，非常非常非常非常感谢波波老师的回答！！！！