type
status
date
slug
summary
tags
category
icon
password
状态
专注质量
预计（分钟）
开始时间
结束时间
文章来源说明
🤔 模块说明
一刷时，到动态规划部分已经结束了。本模块为二刷时，代码随想录新更新的两大模块，随着互联网行业的进一步内卷，图论的题目在笔试中也的确开始频繁出现。
那么接下来，就按照单调栈、图论和并查集的顺序归纳总结。
📝单调栈
单调栈的应用场景
首先看单调栈的模板题：
按照惯例，解决一个算法问题，首先考虑它的暴力解法。这道题的暴力解法当然是遍历数组中每一个元素之后的所有元素，并记录下来，其时间复杂度为O($n^2$)。
单调栈的存在是为了通过一个栈的辅助，用空间换取时间，将时间复杂度降低到O(n)级别。具体操作如下：
- 从数组的第一个元素开始遍历，将其压入栈中。
- 如果当前元素小于等于栈顶元素，将当前元素压入栈中。
- 如果当前元素大于栈顶元素，弹出栈顶元素。这时，就找到了栈顶元素对应的答案。
- 重复第三步，直到所有比当前元素小的栈顶元素全部弹出，然后将当前元素压入栈中。
- 最后，仍留在栈中的元素，其答案都是0，可以在初始化数组时预设。
模板题的变形
下一个更大元素I 力扣题目链接
下一个更大元素II 力扣题目链接
单调栈更多是一种思想，如果掌握了其实解决这两道题也不是很难。
难题
42. 接雨水
84.柱状图中最大的矩形
这两道题看似与单调栈无关，实则有关。需要计算的是中间的凹槽或凸出部分。在实际遇到问题时，可以仔细推演一下：栈中何时应存放元素，如何比较当前元素，以及如何计算答案。解决这几个问题后，即可进行作答。
📝图论
什么时候该想起用图论的相关算法解决问题呢？
之前我们说过，链表、数组、双指针、树的题目都有着明确的特征，图的题目同样也是。
DFS和BFS
DFS，也就是深度优先搜索，表示一直沿着某条路径前行，直到遇到终止条件再回溯。
BFS，也就是广度优先搜索，使用一个队列，将所有当前节点周围的节点全部添加进队列中。这和树的层序遍历很相似，也容易理解。
这部分的题目很多，但基本没有难题，因为核心算法就是这两个，其他部分主要是预处理和后处理。
📝并查集
并查集解决的问题，是判断两个元素在不在一个集合中，以及向集合中添加元素的问题，代码模板如下：
我们可以通过一个数组来实现，数组中的每个元素即表示当前元素的根节点。如果两个节点的根节点相同，那么它们就属于同一个集合。这就像我们存储了若干棵树来表达它们的父子关系。这里的模板代码已经加入了路径压缩，也就是说树的总高度为2。
总之解决的还是图的问题，其中冗余连接II是难题，主要难在思路和情况分类。
🤗总结归纳
单调栈、图论、并查集，这部分题目的核心代码就那么多，重点在于能否想到使用，以及如何使用。这很像编写应用时的工程问题，只需清楚理解情境和最终要求，细心一点，就能达到最后的目标。
致谢：
Written by Aryue,editted by Notion AI.
- 作者:Aryue
- 链接:www.aryue.com/article/396d3c99-b597-4eff-ab9d-3e7853341241
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
相关文章
