DAY20 2026.04.08
LeetCode84 柱状图中最大的矩形 [单调栈]
找左右第一个更小的元素，单调栈从栈顶到栈底递减。栈顶和栈顶的下一个元素以及要入栈的三个元素组成了要求的最大面积的高度和宽度
heights数组末尾要加零，是因为如果数组本身升序，入栈后一定都是单调递减，一直没有计算结果，结尾加个0就会让栈内所有元素进入计算结果的情况
heights数组开头也要加0，是因为如果数组本身降序，例如[8，6，4，2]，在8入栈后，6开始与8比较，此时得到mid(8)，right(6)，但是得不到left。因为此时把mid(8)弹出了，栈内没有元素，为了避免空栈取值会跳过计算结果的逻辑，之后又将6入栈，周而复始
LeetCode207 课程表 [图论、DFS]
题目意思是给你一个有向图，判断图中是否含有环
核心解题思路是，如果在递归过程中发现下一个节点在递归栈中（正在访问中），则找到了环。此处参考灵神的DFS三色标记法
对于每个节点x，都定义三种状态：
- 0：节点x还没被访问到
- 1：节点x正在访问中（正在递归处理节点x以及它的后续节点），dfs(x)尚未结束
- 2：节点x已经完全访问完毕。这也说明从x出发找不到环，所以当我们遇到状态值为2的节点x时，无需递归x
解题流程：
- 根据先修课程数组，构建有向图
- 创建颜色数组colors，长度为课程数量
- 遍历colors数组，如果colors[i]=0，则调用递归函数dfs(i)
- 执行dfs(x)：
- 首先标记colors[x] = 1，表示节点x正在访问中
- 然后遍历x的邻居y。如果colors[y] = 1，则找到环，返回true；如果colors[y] = 0且dfs(y)返回了true，则dfs(x)也返回true
- 如果没找到环，那么先标记colors[x] = 2，表示x已经完全访问完毕，没找到环，然后返回false
- 如果dfs(i)返回true，那么找到了环，则说明课表有问题
- 如果遍历完所有节点也没找到环，则说明课表可行