2024.02.02_学习日记
天气：晴
学习地点：家
学习时长：4h
学习内容
- 滑动窗口（lc239困难）
这个题是滑动窗口问题，如何用On的复杂度返回窗口的最大值最小值，这里用最大值举例。首先生成一个双端队列，双端队列左大右小，每进一个数，跟最右边的数比，如果小，就放右边，如果大，那队列弹出末尾元素，然后继续比较，然后需要删除过期元素以及返回最大值给数组，最后返回res数组即可，双端队列维护的这个区间就是最左边的数是最大值，L往右动一次那么最大值更新一次。最小值的话就是队列从小到大排列。记得看一下python版本。 - 各种数据结构python如何引用
引用链接 - 最小覆盖子串（lc76）
这个题就是用一个字典记录窗口内还需要多少个target的字符数量，分三步，第一步从0开始往右走，直到cnt=0位置，窗口左边界往右动，动到need【c】=0的时候停止，遇到t的元素，然后更新最小值最大值，第三步就是i往下动，need【c】+1，cnt+1，然后右边界继续往右动，最后返回i到j的索引切片，如果j一直没更新还是最大值，那就返回空，没有更新。 - 单调栈
单调栈就是一个栈结构，下面大上面小，遍历一个数组，可以把数组左右边离你最近的更大的数字生成。具体就是如果当前位置比栈顶小就进栈，大的话就弹出栈顶元素，此时栈顶元素下面的位置就是左边最近的，当前位置是右边最近的，然后继续对比，如果小的话就进栈。但是遇到重复值的时候要把下标重叠起来，变成一个集合。 - 接雨水（lc42）
这个题就是用单调栈，当前如果大于单调栈顶，栈顶弹出后左边的值是left，当前值是right，然后左右最小值-栈顶元素高度就是雨水高度，right-left-1就是雨水长度，累加乘起来就行。while中间加了等号，可以排除掉重复元素。