企业官网建设流程全解析

连续区间 + 条件动态变化 → 想滑动窗口。
后进先出 / 配对 / 最近一个更大或更小元素 → 想栈，尤其是单调栈。

复习：

给定一个有序数组：

nums=[1,1,2,2,2,3,4,4]

要求原地删除重复元素，并返回去重后的长度。

例如最终数组前半部分应类似：

[1,2,3,4,...]

先自己判断三件事：

用什么算法/数据结构？ 为什么？ 时间、空间复杂度？

答案
这是典型：

有序数组+原地修改+去重

应该想到：

快慢双指针。

defremoveDuplicates(nums):ifnotnums:return0slow=1forfastinrange(1,len(nums)):ifnums[fast]!=nums[fast-1]:nums[slow]=nums[fast]slow+=1returnslow

时间： 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-left+1]=k

非常简单。

可变长度窗口

例如：

最长无重复子串。

窗口大小根据条件变化：

right 扩张 ↓ 违反条件 ↓ left 收缩 ↓ 再次满足

这是 LeetCode 和机考里更重要的一类。

4. 什么时候想到滑动窗口？

看到这些词马上警觉：

连续子数组 连续子串 最长 最短 至多 K 个 至少…… 无重复 满足某个总和/频率条件

尤其是：

连续+最长/最短

这是超级强的滑动窗口信号。

但是注意：

并不是所有“连续区间”都能滑动窗口。
必须存在某种可维护的性质，使得你知道：
窗口不满足时，该移动哪边

例如数组含大量正负数时，“和太大就移动左边”往往不成立，因为移除一个负数反而可能让和变大。

5. Python 常用窗口工具

left=0forrightinrange(len(nums)):# 把nums[right] 加入窗口while窗口不满足条件：# 移除nums[left]left+=1#记录答案

可变窗口的经典模版

完整例题｜LeetCode 3. 无重复字符的最长子串

classSolution:deflengthOfLongestSubstring(self,s:str)->int:seen=set()left=0ans=0forrightinrange(len(s)):whiles[right]inseen:seen.remove(s[left])# 因为是连续的区间，所以不能只移除那个重复的字符left+=1seen.add(s[right])ans=max(ans,right-left+1)# 记录最大的结果returnans

每个字符：

最多进入窗口一次 最多离开窗口一次

因此两个指针总移动次数最多约：

2n

所以：

O(n)

额外空间：

O(min(n,字符集大小))

优化

用last字典记录上一个字符出现的位置
当遇到重复字符的时候，直接把left跳到上一次出现位置的右边，不需要一个一个慢慢挪动。

deflengthOfLongestSubstring(s):last={}#记录字符，最后一次出现的索引left=0#窗口的左边界ans=0# 最长长度forright,chinenumerate(s):#right是当前右指针的位置，ch是当前字符ifchinlast:left=max(left,last[ch]+1)# !!! 上一次出现位置的右边#因为 last[ch] + 1可能比当前 left还小（那个重复字符在 left 左边很远，已经不在当前窗口里了），这时候不能把 left 往回退，所以取 max 保证 left 只往前走、不后退。last[ch]=right ans=max(ans,right-left+1)#当前窗口 [left, right]的长度，和之前的最大值比。returnans

enumerate(s)返回一个迭代器，每次产出一对值：
(索引, 元素)
for right, ch是 元组解包，把这一对值分别赋给 right和 ch。

Part B｜栈

1. 栈是什么？

栈： Last In,First Out，后进先出。

想象一摞盘子：

最后放上去的
最先拿出来

Python 通常直接： stack=[]入栈： stack.append(x)出栈： stack.pop()查看栈顶： stack[-1]

复杂度通常：

push：O(1)pop：O(1)top：O(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:prev=stack.pop()ans[prev]=i-prev stack.append(i)returnans# 用一个栈维护还没找到更高温度的日期索引，栈里存的温度是从底到顶递减的。# 当今天温度比栈顶那天高的时候，说明找到了栈顶那天的答案，单独并计算天数差。

为什么是O(n)?
因为每个下标入栈一次，出栈最多一次，所以总操作<=2n ,因此O(n)
空间O(n)

练习题

20→209→209长度变体思考 →496→438

练习 1｜LeetCode 20. 有效的括号

左括号 → push 右括号 → pop+检查 最后 stack 必须为空

classSolution:defisValid(self,s:str)->bool:# 遇到左括号就压栈，遇到右括号就检查栈顶是否是对应的左括号。能配对就弹出，不能配对就无效stack=[]#左括号：对应的右括号mapping={')':'()',']':'[','}':'{'}forchins:ifchinmapping:# 右括号top=stack.pop()ifstackelse'#'#如果栈为空的话就弹出一个假值，保证能够比较ifmapping[ch]!=top:returnFalse# 类型不匹配else:stack.append(ch)returnlen(stack)==0#全部匹配完成，栈应该为空

练习 2｜LeetCode 209. 长度最小的子数组

连续 最短 数组全是正数

classSolution:defminSubArrayLen(self,target:int,nums:List[int])->int:# 右指针不断扩张窗口，当窗口内的元素大雨target时，记录长度，然后左指针收缩窗口，尝试找到更短的子数组left=0window_sum=0min_len=float('inf')#记录最短长度forrightinrange(len(nums)):window_sum+=nums[right]#扩张窗口whilewindow_sum>=target:#当和满足条件时，尝试收缩左边界min_len=min(min_len,right-left+1)window_sum-=nums[left]#收缩之前先减left+=1returnmin_lenifmin_len!=float('inf')else0

练习 3｜LeetCode 496. 下一个更大元素 I 单调递减栈
它右边第一个比它大的元素。

classSolution:defnextGreaterElement(self,nums1:List[int],nums2:List[int])->List[int]:#单调栈+哈希表next_greater={}stack=[]#对nums2用单调栈：fornuminnums2:whilestackandstack[-1]<num:prev=stack.pop()next_greater[prev]=num stack.append(num)# 查表return[next_greater.get(num,-1)fornuminnums1]# 单调栈算"下一个更大元素"，哈希表存结果，查表输出。# .get(key, default)是字典的方法，意思是查字典里有没有 key，有就返回对应的值；没有就返回 default

练习 4｜LeetCode 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_count：a:1, b:1, c:1# 初始化第一个窗口 s[0:len(p)]foriinrange(len(p)):w_count[ord(s[i])-ord('a')]+=1ifw_count==p_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_count==p_count:res.append(i-len(p)+1)returnres# 时间：O(n)，n = len(s)，每个字符进窗口一次、出窗口一次# 空间：O(1)（26 个字母的常数空间

fromcollectionsimportCounterdeffindAnagrams(s,p):iflen(p)>len(s):return[]need=Counter(p)window=Counter()left=0ans=[]forright,chinenumerate(s):window[ch]+=1ifright-left+1>len(p):old=s[left]window[old]-=1ifwindow[old]==0:delwindow[old]left+=1ifwindow==need:ans.append(left)returnans

ACM 训练（输入输出）

输入一行字符串，求无重复字符的最长连续子串长度。

s=input().strip()seen=set()left=0right=0ans=0forrightinrange(lens(s)):whiles[right]inseen:seen.remove(s[left])left+=1seen.add(s[right])ans=max(ans,right-left+1)print(ans)

真实机试的时候往往需要自己处理：

inputsplit 类型转换 输出

面试手撕训练｜LeetCode 739 每日温度

今天要求你练习完整口述。

① 暴力

对每一天向后扫描，找到第一个更高温度，最坏需要 O(n²)。

② 瓶颈

对很多元素重复扫描了相同的后续区间。

③ 优化

我可以维护一个单调递减栈，保存仍然没有找到更高温度的下标。

④ 当前温度更高时

当前温度就是栈顶元素遇到的第一个更高温度，所以不断弹栈并计算下标差。

⑤ 复杂度

每个元素最多入栈和出栈各一次，所以时间 O(n)，额外空间 O(n)。

⑥ 为什么保存下标？

因为题目最终需要计算等待的天数，也就是两个位置的距离。

Day 2 Cheat Sheet

滑动窗口识别信号

看到：

连续 子数组/子串 最长/最短 至多 K 至少…… 窗口内频率 无重复

优先检查滑动窗口。

经典模板：

left=0forrightinrange(len(nums)):加入 nums[rtight]while窗口不合法:remove nums[left]left+=1update the answer

核心问题始终只有三个：
窗口里维护什么？什么时候扩？什么时候缩？

普通栈识别信号

括号 嵌套 后进先出 撤销 表达式 路径

模板：

stack=[]stack.append(x)x=stack.pop()top=stack[-1]

单调栈识别信号

看到：

下一个更大 下一个更小 右边第一个更大 左边第一个更小 最近的……

强烈考虑单调栈。

stack=[]fori,xinenumberate(nums):whilestackandnums[stack[-1]]<x:j=stack.pop()# x slove the answer of jstack.append(i)

今天最容易犯的错误

一看到 for + while 就判断滑动窗口是 O(n²)；要看每个元素实际被访问多少次。
滑动窗口只会背模板，却不知道窗口里到底维护的是 sum、set 还是 frequency。
数组有负数时仍然机械使用“和太大就缩左边”的窗口逻辑。
普通栈和单调栈混淆：单调栈的核心不是 LIFO，而是维护顺序以解决最近更大/更小问题。
单调栈只存值，但题目要求距离时才发现自己需要的是下标。
while stack and … 忘写 stack 判断，直接访问空栈。
觉得单调栈是“神奇模板”，却说不清为什么每个元素最多入栈、出栈一次。

今天真正带走两个判断就够了：

连续区间 + 条件可以通过左右移动维护 → 滑动窗口。
需要找最近/下一个更大或更小元素 → 单调栈。