连续区间 条件动态变化 → 想滑动窗口。后进先出 / 配对 / 最近一个更大或更小元素 → 想栈尤其是单调栈。复习给定一个有序数组nums[1,1,2,2,2,3,4,4]要求原地删除重复元素并返回去重后的长度。例如最终数组前半部分应类似[1,2,3,4,...]先自己判断三件事用什么算法/数据结构 为什么 时间、空间复杂度答案这是典型有序数组原地修改去重应该想到快慢双指针。defremoveDuplicates(nums):ifnotnums:return0slow1forfastinrange(1,len(nums)):ifnums[fast]!nums[fast-1]:nums[slow]nums[fast]slow1returnslow时间 O(n)额外空间 O(1)如果你第一反应是 set(nums)结果虽然能去重但题目要求原地修改且保持顺序就不是最佳答案。Part A滑动窗口1. 滑动窗口到底是什么滑动窗口本质上是用两个指针维护一个连续区间并在指针移动过程中动态维护这个区间的状态。形式[left........right]与昨天普通双指针最大的区别双指针强调 两个位置如何移动。滑动窗口强调 left 和 right 之间这一整个连续区域当前满足什么条件。例如a b c a b↑ ↑ left right窗口可能表示当前无重复字符区间或者当前总和target 的区间2. 为什么需要滑动窗口来看一个经典问题找数组中满足某条件的最短连续子数组。暴力做法枚举起点i再枚举终点j复杂度O(n²)如果还计算区间内部信息甚至可能到O(n³)但很多连续区间问题有这样的性质右边加入一个元素 ↓ 窗口状态变化 不满足条件 ↓ 不断移动左边于是right 从左到右走一次 left 也最多走一次总复杂度通常O(n)3. 两种核心窗口固定长度窗口例如长度为 k 的连续子数组最大和。窗口永远[right-left1]k非常简单。可变长度窗口例如最长无重复子串。窗口大小根据条件变化right 扩张 ↓ 违反条件 ↓ left 收缩 ↓ 再次满足这是 LeetCode 和机考里更重要的一类。4. 什么时候想到滑动窗口看到这些词马上警觉连续子数组 连续子串 最长 最短 至多 K 个 至少…… 无重复 满足某个总和/频率条件尤其是连续最长/最短这是超级强的滑动窗口信号。但是注意并不是所有“连续区间”都能滑动窗口。必须存在某种可维护的性质使得你知道窗口不满足时该移动哪边例如数组含大量正负数时“和太大就移动左边”往往不成立因为移除一个负数反而可能让和变大。5. Python 常用窗口工具left0forrightinrange(len(nums)):# 把nums[right] 加入窗口while窗口不满足条件# 移除nums[left]left1#记录答案可变窗口的经典模版完整例题LeetCode 3. 无重复字符的最长子串classSolution:deflengthOfLongestSubstring(self,s:str)-int:seenset()left0ans0forrightinrange(len(s)):whiles[right]inseen:seen.remove(s[left])# 因为是连续的区间所以不能只移除那个重复的字符left1seen.add(s[right])ansmax(ans,right-left1)# 记录最大的结果returnans每个字符最多进入窗口一次 最多离开窗口一次因此两个指针总移动次数最多约2n所以O(n)额外空间O(min(n,字符集大小))优化用last字典记录上一个字符出现的位置当遇到重复字符的时候直接把left跳到上一次出现位置的右边不需要一个一个慢慢挪动。deflengthOfLongestSubstring(s):last{}#记录字符最后一次出现的索引left0#窗口的左边界ans0# 最长长度forright,chinenumerate(s):#right是当前右指针的位置ch是当前字符ifchinlast:leftmax(left,last[ch]1)# !!! 上一次出现位置的右边#因为 last[ch] 1可能比当前 left还小那个重复字符在 left 左边很远已经不在当前窗口里了这时候不能把 left 往回退所以取 max 保证 left 只往前走、不后退。last[ch]right ansmax(ans,right-left1)#当前窗口 [left, right]的长度和之前的最大值比。returnansenumerate(s)返回一个迭代器每次产出一对值(索引, 元素)for right, ch是 元组解包把这一对值分别赋给 right和 ch。Part B栈1. 栈是什么栈 Last In,First Out后进先出。想象一摞盘子最后放上去的最先拿出来Python 通常直接 stack[]入栈 stack.append(x)出栈 stack.pop()查看栈顶 stack[-1]复杂度通常pushO(1)popO(1)topO(1)2. 什么题该想到普通栈典型关键词括号匹配 嵌套结构 撤销 表达式计算 后进先出 递归模拟 路径简化3. 单调栈是什么这一步很重要。普通栈只是 后进先出 单调栈额外要求 栈内元素始终保持单调递增或单调递减。例如1,3,5,8是递增栈。或者9,7,4,2是递减栈。4. 单调栈到底解决什么它最擅长的是快速寻找某个元素左边/右边第一个更大或更小的元素。看到下一个更大元素 右边第一个比它大 左边最近一个比它小 每日温度多久后升高 柱状图面积脑子直接单调栈。5. 为什么不用暴力比如temperatures[73,74,75,71,69,72,76,73]问每一天后面多少天会出现更高温暴力第1天向后找 第2天向后找 第3天向后找...最坏O(n²)单调栈可以O(n)因为每个元素最多入栈一次 最多出栈一次LeetCode 739. 每日温度classSolution:defdailyTemperatures(self,temperatures:List[int])-List[int]:ans[0]*len(temperatures)#初始化为0stack[]fori,tempinenumerate(temperatures):whilestackandtemperatures[stack[-1]]temp:prevstack.pop()ans[prev]i-prev stack.append(i)returnans# 用一个栈维护还没找到更高温度的日期索引栈里存的温度是从底到顶递减的。# 当今天温度比栈顶那天高的时候说明找到了栈顶那天的答案单独并计算天数差。为什么是O(n)?因为每个下标入栈一次出栈最多一次所以总操作2n ,因此O(n)空间O(n)练习题20→209→209长度变体思考 →496→438练习 1LeetCode 20. 有效的括号左括号 → push 右括号 → pop检查 最后 stack 必须为空classSolution:defisValid(self,s:str)-bool:# 遇到左括号就压栈遇到右括号就检查栈顶是否是对应的左括号。能配对就弹出不能配对就无效stack[]#左括号对应的右括号mapping{):(),]:[,}:{}forchins:ifchinmapping:# 右括号topstack.pop()ifstackelse##如果栈为空的话就弹出一个假值保证能够比较ifmapping[ch]!top:returnFalse# 类型不匹配else:stack.append(ch)returnlen(stack)0#全部匹配完成栈应该为空练习 2LeetCode 209. 长度最小的子数组连续 最短 数组全是正数classSolution:defminSubArrayLen(self,target:int,nums:List[int])-int:# 右指针不断扩张窗口当窗口内的元素大雨target时记录长度然后左指针收缩窗口尝试找到更短的子数组left0window_sum0min_lenfloat(inf)#记录最短长度forrightinrange(len(nums)):window_sumnums[right]#扩张窗口whilewindow_sumtarget:#当和满足条件时尝试收缩左边界min_lenmin(min_len,right-left1)window_sum-nums[left]#收缩之前先减left1returnmin_lenifmin_len!float(inf)else0练习 3LeetCode 496. 下一个更大元素 I 单调递减栈它右边第一个比它大的元素。classSolution:defnextGreaterElement(self,nums1:List[int],nums2:List[int])-List[int]:#单调栈哈希表next_greater{}stack[]#对nums2用单调栈fornuminnums2:whilestackandstack[-1]num:prevstack.pop()next_greater[prev]num stack.append(num)# 查表return[next_greater.get(num,-1)fornuminnums1]# 单调栈算下一个更大元素哈希表存结果查表输出。# .get(key, default)是字典的方法意思是查字典里有没有 key有就返回对应的值没有就返回 default练习 4LeetCode 438. 找到字符串中所有字母异位词classSolution:deffindAnagrams(self,s:str,p:str)-List[int]:# 固定长度滑动窗口 哈希计数。iflen(p)len(s):return[]p_count[0]*26w_count[0]*26res[]# p_count是一个长度为 26 的数组每个位置对应一个字母的出现次数# 把字母 ch映射成 0~25 的下标然后在对应的计数器上加 1。# ord()返回字符的 ASCII 码值forchinp:p_count[ord(ch)-ord(a)]1# p_counta:1, b:1, c:1# 初始化第一个窗口 s[0:len(p)]foriinrange(len(p)):w_count[ord(s[i])-ord(a)]1ifw_countp_count:res.append(0)#滑动窗口foriinrange(len(p),len(s)):#右边新字符进窗口w_count[ord(s[i])-ord(a)]1#左边旧字符出窗口w_count[ord(s[i-len(p)])-ord(a)]-1ifw_countp_count:res.append(i-len(p)1)returnres# 时间O(n)n len(s)每个字符进窗口一次、出窗口一次# 空间O(1)26 个字母的常数空间fromcollectionsimportCounterdeffindAnagrams(s,p):iflen(p)len(s):return[]needCounter(p)windowCounter()left0ans[]forright,chinenumerate(s):window[ch]1ifright-left1len(p):olds[left]window[old]-1ifwindow[old]0:delwindow[old]left1ifwindowneed:ans.append(left)returnansACM 训练输入输出输入一行字符串求无重复字符的最长连续子串长度。sinput().strip()seenset()left0right0ans0forrightinrange(lens(s)):whiles[right]inseen:seen.remove(s[left])left1seen.add(s[right])ansmax(ans,right-left1)print(ans)真实机试的时候往往需要自己处理inputsplit 类型转换 输出面试手撕训练LeetCode 739 每日温度今天要求你练习完整口述。① 暴力对每一天向后扫描找到第一个更高温度最坏需要 O(n²)。② 瓶颈对很多元素重复扫描了相同的后续区间。③ 优化我可以维护一个单调递减栈保存仍然没有找到更高温度的下标。④ 当前温度更高时当前温度就是栈顶元素遇到的第一个更高温度所以不断弹栈并计算下标差。⑤ 复杂度每个元素最多入栈和出栈各一次所以时间 O(n)额外空间 O(n)。⑥ 为什么保存下标因为题目最终需要计算等待的天数也就是两个位置的距离。Day 2 Cheat Sheet滑动窗口识别信号看到连续 子数组/子串 最长/最短 至多 K 至少…… 窗口内频率 无重复优先检查滑动窗口。经典模板left0forrightinrange(len(nums)):加入 nums[rtight]while窗口不合法:remove nums[left]left1update the answer核心问题始终只有三个窗口里维护什么什么时候扩什么时候缩普通栈识别信号括号 嵌套 后进先出 撤销 表达式 路径模板stack[]stack.append(x)xstack.pop()topstack[-1]单调栈识别信号看到下一个更大 下一个更小 右边第一个更大 左边第一个更小 最近的……强烈考虑单调栈。stack[]fori,xinenumberate(nums):whilestackandnums[stack[-1]]x:jstack.pop()# x slove the answer of jstack.append(i)今天最容易犯的错误一看到 for while 就判断滑动窗口是 O(n²)要看每个元素实际被访问多少次。滑动窗口只会背模板却不知道窗口里到底维护的是 sum、set 还是 frequency。数组有负数时仍然机械使用“和太大就缩左边”的窗口逻辑。普通栈和单调栈混淆单调栈的核心不是 LIFO而是维护顺序以解决最近更大/更小问题。单调栈只存值但题目要求距离时才发现自己需要的是下标。while stack and … 忘写 stack 判断直接访问空栈。觉得单调栈是“神奇模板”却说不清为什么每个元素最多入栈、出栈一次。今天真正带走两个判断就够了连续区间 条件可以通过左右移动维护 → 滑动窗口。需要找最近/下一个更大或更小元素 → 单调栈。
算法 Day 2 滑动窗口 + 栈 / 单调栈
连续区间 条件动态变化 → 想滑动窗口。后进先出 / 配对 / 最近一个更大或更小元素 → 想栈尤其是单调栈。复习给定一个有序数组nums[1,1,2,2,2,3,4,4]要求原地删除重复元素并返回去重后的长度。例如最终数组前半部分应类似[1,2,3,4,...]先自己判断三件事用什么算法/数据结构 为什么 时间、空间复杂度答案这是典型有序数组原地修改去重应该想到快慢双指针。defremoveDuplicates(nums):ifnotnums:return0slow1forfastinrange(1,len(nums)):ifnums[fast]!nums[fast-1]:nums[slow]nums[fast]slow1returnslow时间 O(n)额外空间 O(1)如果你第一反应是 set(nums)结果虽然能去重但题目要求原地修改且保持顺序就不是最佳答案。Part A滑动窗口1. 滑动窗口到底是什么滑动窗口本质上是用两个指针维护一个连续区间并在指针移动过程中动态维护这个区间的状态。形式[left........right]与昨天普通双指针最大的区别双指针强调 两个位置如何移动。滑动窗口强调 left 和 right 之间这一整个连续区域当前满足什么条件。例如a b c a b↑ ↑ left right窗口可能表示当前无重复字符区间或者当前总和target 的区间2. 为什么需要滑动窗口来看一个经典问题找数组中满足某条件的最短连续子数组。暴力做法枚举起点i再枚举终点j复杂度O(n²)如果还计算区间内部信息甚至可能到O(n³)但很多连续区间问题有这样的性质右边加入一个元素 ↓ 窗口状态变化 不满足条件 ↓ 不断移动左边于是right 从左到右走一次 left 也最多走一次总复杂度通常O(n)3. 两种核心窗口固定长度窗口例如长度为 k 的连续子数组最大和。窗口永远[right-left1]k非常简单。可变长度窗口例如最长无重复子串。窗口大小根据条件变化right 扩张 ↓ 违反条件 ↓ left 收缩 ↓ 再次满足这是 LeetCode 和机考里更重要的一类。4. 什么时候想到滑动窗口看到这些词马上警觉连续子数组 连续子串 最长 最短 至多 K 个 至少…… 无重复 满足某个总和/频率条件尤其是连续最长/最短这是超级强的滑动窗口信号。但是注意并不是所有“连续区间”都能滑动窗口。必须存在某种可维护的性质使得你知道窗口不满足时该移动哪边例如数组含大量正负数时“和太大就移动左边”往往不成立因为移除一个负数反而可能让和变大。5. Python 常用窗口工具left0forrightinrange(len(nums)):# 把nums[right] 加入窗口while窗口不满足条件# 移除nums[left]left1#记录答案可变窗口的经典模版完整例题LeetCode 3. 无重复字符的最长子串classSolution:deflengthOfLongestSubstring(self,s:str)-int:seenset()left0ans0forrightinrange(len(s)):whiles[right]inseen:seen.remove(s[left])# 因为是连续的区间所以不能只移除那个重复的字符left1seen.add(s[right])ansmax(ans,right-left1)# 记录最大的结果returnans每个字符最多进入窗口一次 最多离开窗口一次因此两个指针总移动次数最多约2n所以O(n)额外空间O(min(n,字符集大小))优化用last字典记录上一个字符出现的位置当遇到重复字符的时候直接把left跳到上一次出现位置的右边不需要一个一个慢慢挪动。deflengthOfLongestSubstring(s):last{}#记录字符最后一次出现的索引left0#窗口的左边界ans0# 最长长度forright,chinenumerate(s):#right是当前右指针的位置ch是当前字符ifchinlast:leftmax(left,last[ch]1)# !!! 上一次出现位置的右边#因为 last[ch] 1可能比当前 left还小那个重复字符在 left 左边很远已经不在当前窗口里了这时候不能把 left 往回退所以取 max 保证 left 只往前走、不后退。last[ch]right ansmax(ans,right-left1)#当前窗口 [left, right]的长度和之前的最大值比。returnansenumerate(s)返回一个迭代器每次产出一对值(索引, 元素)for right, ch是 元组解包把这一对值分别赋给 right和 ch。Part B栈1. 栈是什么栈 Last In,First Out后进先出。想象一摞盘子最后放上去的最先拿出来Python 通常直接 stack[]入栈 stack.append(x)出栈 stack.pop()查看栈顶 stack[-1]复杂度通常pushO(1)popO(1)topO(1)2. 什么题该想到普通栈典型关键词括号匹配 嵌套结构 撤销 表达式计算 后进先出 递归模拟 路径简化3. 单调栈是什么这一步很重要。普通栈只是 后进先出 单调栈额外要求 栈内元素始终保持单调递增或单调递减。例如1,3,5,8是递增栈。或者9,7,4,2是递减栈。4. 单调栈到底解决什么它最擅长的是快速寻找某个元素左边/右边第一个更大或更小的元素。看到下一个更大元素 右边第一个比它大 左边最近一个比它小 每日温度多久后升高 柱状图面积脑子直接单调栈。5. 为什么不用暴力比如temperatures[73,74,75,71,69,72,76,73]问每一天后面多少天会出现更高温暴力第1天向后找 第2天向后找 第3天向后找...最坏O(n²)单调栈可以O(n)因为每个元素最多入栈一次 最多出栈一次LeetCode 739. 每日温度classSolution:defdailyTemperatures(self,temperatures:List[int])-List[int]:ans[0]*len(temperatures)#初始化为0stack[]fori,tempinenumerate(temperatures):whilestackandtemperatures[stack[-1]]temp:prevstack.pop()ans[prev]i-prev stack.append(i)returnans# 用一个栈维护还没找到更高温度的日期索引栈里存的温度是从底到顶递减的。# 当今天温度比栈顶那天高的时候说明找到了栈顶那天的答案单独并计算天数差。为什么是O(n)?因为每个下标入栈一次出栈最多一次所以总操作2n ,因此O(n)空间O(n)练习题20→209→209长度变体思考 →496→438练习 1LeetCode 20. 有效的括号左括号 → push 右括号 → pop检查 最后 stack 必须为空classSolution:defisValid(self,s:str)-bool:# 遇到左括号就压栈遇到右括号就检查栈顶是否是对应的左括号。能配对就弹出不能配对就无效stack[]#左括号对应的右括号mapping{):(),]:[,}:{}forchins:ifchinmapping:# 右括号topstack.pop()ifstackelse##如果栈为空的话就弹出一个假值保证能够比较ifmapping[ch]!top:returnFalse# 类型不匹配else:stack.append(ch)returnlen(stack)0#全部匹配完成栈应该为空练习 2LeetCode 209. 长度最小的子数组连续 最短 数组全是正数classSolution:defminSubArrayLen(self,target:int,nums:List[int])-int:# 右指针不断扩张窗口当窗口内的元素大雨target时记录长度然后左指针收缩窗口尝试找到更短的子数组left0window_sum0min_lenfloat(inf)#记录最短长度forrightinrange(len(nums)):window_sumnums[right]#扩张窗口whilewindow_sumtarget:#当和满足条件时尝试收缩左边界min_lenmin(min_len,right-left1)window_sum-nums[left]#收缩之前先减left1returnmin_lenifmin_len!float(inf)else0练习 3LeetCode 496. 下一个更大元素 I 单调递减栈它右边第一个比它大的元素。classSolution:defnextGreaterElement(self,nums1:List[int],nums2:List[int])-List[int]:#单调栈哈希表next_greater{}stack[]#对nums2用单调栈fornuminnums2:whilestackandstack[-1]num:prevstack.pop()next_greater[prev]num stack.append(num)# 查表return[next_greater.get(num,-1)fornuminnums1]# 单调栈算下一个更大元素哈希表存结果查表输出。# .get(key, default)是字典的方法意思是查字典里有没有 key有就返回对应的值没有就返回 default练习 4LeetCode 438. 找到字符串中所有字母异位词classSolution:deffindAnagrams(self,s:str,p:str)-List[int]:# 固定长度滑动窗口 哈希计数。iflen(p)len(s):return[]p_count[0]*26w_count[0]*26res[]# p_count是一个长度为 26 的数组每个位置对应一个字母的出现次数# 把字母 ch映射成 0~25 的下标然后在对应的计数器上加 1。# ord()返回字符的 ASCII 码值forchinp:p_count[ord(ch)-ord(a)]1# p_counta:1, b:1, c:1# 初始化第一个窗口 s[0:len(p)]foriinrange(len(p)):w_count[ord(s[i])-ord(a)]1ifw_countp_count:res.append(0)#滑动窗口foriinrange(len(p),len(s)):#右边新字符进窗口w_count[ord(s[i])-ord(a)]1#左边旧字符出窗口w_count[ord(s[i-len(p)])-ord(a)]-1ifw_countp_count:res.append(i-len(p)1)returnres# 时间O(n)n len(s)每个字符进窗口一次、出窗口一次# 空间O(1)26 个字母的常数空间fromcollectionsimportCounterdeffindAnagrams(s,p):iflen(p)len(s):return[]needCounter(p)windowCounter()left0ans[]forright,chinenumerate(s):window[ch]1ifright-left1len(p):olds[left]window[old]-1ifwindow[old]0:delwindow[old]left1ifwindowneed:ans.append(left)returnansACM 训练输入输出输入一行字符串求无重复字符的最长连续子串长度。sinput().strip()seenset()left0right0ans0forrightinrange(lens(s)):whiles[right]inseen:seen.remove(s[left])left1seen.add(s[right])ansmax(ans,right-left1)print(ans)真实机试的时候往往需要自己处理inputsplit 类型转换 输出面试手撕训练LeetCode 739 每日温度今天要求你练习完整口述。① 暴力对每一天向后扫描找到第一个更高温度最坏需要 O(n²)。② 瓶颈对很多元素重复扫描了相同的后续区间。③ 优化我可以维护一个单调递减栈保存仍然没有找到更高温度的下标。④ 当前温度更高时当前温度就是栈顶元素遇到的第一个更高温度所以不断弹栈并计算下标差。⑤ 复杂度每个元素最多入栈和出栈各一次所以时间 O(n)额外空间 O(n)。⑥ 为什么保存下标因为题目最终需要计算等待的天数也就是两个位置的距离。Day 2 Cheat Sheet滑动窗口识别信号看到连续 子数组/子串 最长/最短 至多 K 至少…… 窗口内频率 无重复优先检查滑动窗口。经典模板left0forrightinrange(len(nums)):加入 nums[rtight]while窗口不合法:remove nums[left]left1update the answer核心问题始终只有三个窗口里维护什么什么时候扩什么时候缩普通栈识别信号括号 嵌套 后进先出 撤销 表达式 路径模板stack[]stack.append(x)xstack.pop()topstack[-1]单调栈识别信号看到下一个更大 下一个更小 右边第一个更大 左边第一个更小 最近的……强烈考虑单调栈。stack[]fori,xinenumberate(nums):whilestackandnums[stack[-1]]x:jstack.pop()# x slove the answer of jstack.append(i)今天最容易犯的错误一看到 for while 就判断滑动窗口是 O(n²)要看每个元素实际被访问多少次。滑动窗口只会背模板却不知道窗口里到底维护的是 sum、set 还是 frequency。数组有负数时仍然机械使用“和太大就缩左边”的窗口逻辑。普通栈和单调栈混淆单调栈的核心不是 LIFO而是维护顺序以解决最近更大/更小问题。单调栈只存值但题目要求距离时才发现自己需要的是下标。while stack and … 忘写 stack 判断直接访问空栈。觉得单调栈是“神奇模板”却说不清为什么每个元素最多入栈、出栈一次。今天真正带走两个判断就够了连续区间 条件可以通过左右移动维护 → 滑动窗口。需要找最近/下一个更大或更小元素 → 单调栈。
