Algorithms / LeetCode
算法刷题模型整理（七）
按链表、数组、哈希表、字符串等主题整理常见题型、核心思路和易错点。
单调栈
LC739 每日温度
解题模型：
数组
核心思路：
遍历数组，维护单调栈，存放栈底到栈顶温度递减的下标，遇到比栈顶温度大的就弹栈进行计算，栈空或温度小于栈顶就压栈
易错点：
- 栈内存放的是下标
- 用while而不是if判断，防止漏元素
LC042 接雨水
解题模型：
数组
核心思路：
遍历数组，维护单调栈，存放栈底到栈顶高度递减的下标，空栈或高度小于栈顶就压栈，遇到高度大于栈顶时，若栈内元素为1则直接弹栈，再把当前元素压栈重新计算，栈内元素数量大于等于2时获取栈顶元素后弹栈，记为bottom，此时新的栈顶元素为左壁，遍历到的当前元素为右壁，进行计算
易错点：
- 体积计算，高度为左右壁更低的那个，宽为右壁减左壁
- 注意栈内元素数量大于1和等于1的情况
图论
LC200 岛屿数量
解题模型：
dfs
核心思路：
遍历网格，从任意1节点开始深搜，上下左右都能进下一层，遍历过的节点都改成0，完成深搜后答案加1，继续遍历网格直到下一个1节点
易错点：
- 本题网格中的为字符，注意判断时的写法
- 深搜时注意边界
LC207 课程表
解题模型：
dfs
核心思路：
先用邻接表储存图，每个节点指向自己的前置节点，然后维护visit数组记录每个节点的搜索状态，初始为0代表未访问，选择任意未访问节点进行深搜，进入搜索时标记为1表示正在搜索，然后进行深搜，返回时标记为2表示搜索完成，若在搜索时遇到标记为1的节点说明出现了环，无法进行拓扑排序，返回false
易错点：
- 本题设置邻接表、答案状态变量、visit数组为全局变量更加方便，dfs只需节点下标一个参数
- 下标的区分较为复杂