连续区间 + 条件动态变化 → 想滑动窗口。
后进先出 / 配对 / 最近一个更大或更小元素 → 想栈，尤其是单调栈。
复习：
给定一个有序数组：
nums = [1, 1, 2, 2, 2, 3, 4, 4]
要求原地删除重复元素，并返回去重后的长度。
例如最终数组前半部分应类似：
[1,2,3,4,...]
先自己判断三件事：
用什么算法/数据结构？
为什么？
时间、空间复杂度？
答案
这是典型：
有序数组 + 原地修改 + 去重
应该想到：
快慢双指针。
def removeDuplicates(nums):
if not nums:
return 0
slow = 1
for fast in range(1, len(nums)):
if nums[fast] != nums[fast - 1]:
nums[slow] = nums[fast]
slow += 1
return slow
时间：
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 = 0
for right in range(len(nums)):
# 把nums[right] 加入窗口
while 窗口不满足条件：
# 移除nums[left]
left += 1
#记录答案
可变窗口的经典模版
完整例题｜LeetCode 3. 无重复字符的最长子串
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
seen = set ()
left = 0
ans = 0
for right in range(len(s)):
while s[right] in seen :
seen.remove(s[left]) # 因为是连续的区间，所以不能只移除那个重复的字符
left += 1
seen.add(s[right])
ans = max(ans, right - left +1) # 记录最大的结果
return ans
每个字符：
最多进入窗口一次
最多离开窗口一次
因此两个指针总移动次数最多约：
2n
所以：
O(n)
额外空间：
O(min(n, 字符集大小))
优化
用last字典记录上一个字符出现的位置
当遇到重复字符的时候，直接把left跳到上一次出现位置的右边，不需要一个一个慢慢挪动。
def lengthOfLongestSubstring(s):
last = {} #记录字符，最后一次出现的索引
left = 0 #窗口的左边界
ans = 0 # 最长长度
for right , ch in enumerate(s): #right是当前右指针的位置，ch是当前字符
if ch in last :
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]的长度，和之前的最大值比。
return ans
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. 每日温度
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
ans = [0] * len(temperatures) #初始化为0
stack = []
for i , temp in enumerate(temperatures):
while stack and temperatures[stack[-1]]<temp:
prev = stack.pop()
ans[prev] = i - prev
stack.append(i)
return ans
# 用一个栈维护还没找到更高温度的日期索引，栈里存的温度是从底到顶递减的。
# 当今天温度比栈顶那天高的时候，说明找到了栈顶那天的答案，单独并计算天数差。
为什么是O(n)?
因为每个下标入栈一次，出栈最多一次，所以总操作<=2n ,因此O(n)
空间O(n)
练习题
20 → 209 → 209长度变体思考 → 496 → 438
练习 1｜LeetCode 20. 有效的括号
左括号 → push
右括号 → pop + 检查
最后 stack 必须为空
class Solution:
def isValid(self, s: str) -> bool:
# 遇到左括号就压栈，遇到右括号就检查栈顶是否是对应的左括号。能配对就弹出，不能配对就无效
stack = []
#左括号：对应的右括号
mapping = {')':'()', ']':'[' , '}':'{'}
for ch in s :
if ch in mapping: # 右括号
top = stack.pop() if stack else '#' #如果栈为空的话就弹出一个假值，保证能够比较
if mapping[ch] != top :
return False # 类型不匹配
else :
stack.append(ch)
return len(stack) == 0 #全部匹配完成，栈应该为空
练习 2｜LeetCode 209. 长度最小的子数组
连续
最短
数组全是正数
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
# 右指针不断扩张窗口，当窗口内的元素大雨target时，记录长度，然后左指针收缩窗口，尝试找到更短的子数组
left = 0
window_sum = 0
min_len = float('inf') #记录最短长度
for right in range(len(nums)):
window_sum += nums[right] #扩张窗口
while window_sum >= target :
#当和满足条件时，尝试收缩左边界
min_len = min(min_len , right - left +1)
window_sum -= nums[left] #收缩之前先减
left += 1
return min_len if min_len != float('inf') else 0
练习 3｜LeetCode 496. 下一个更大元素 I 单调递减栈
它右边第一个比它大的元素。
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
#单调栈+哈希表
next_greater = {}
stack = []
#对nums2用单调栈：
for num in nums2:
while stack and stack[-1] <num :
prev = stack.pop()
next_greater[prev] = num
stack.append(num)
# 查表
return [next_greater.get(num , -1) for num in nums1]
# 单调栈算"下一个更大元素"，哈希表存结果，查表输出。
# .get(key, default)是字典的方法，意思是查字典里有没有 key，有就返回对应的值；没有就返回 default
练习 4｜LeetCode 438. 找到字符串中所有字母异位词
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
# 固定长度滑动窗口 + 哈希计数。
if len(p) > len(s):
return []
p_count = [0] *26
w_count = [0] *26
res = []
# p_count是一个长度为 26 的数组，每个位置对应一个字母的出现次数：
# 把字母 ch映射成 0~25 的下标，然后在对应的计数器上加 1。
# ord()返回字符的 ASCII 码值：
for ch in p :
p_count[ord(ch) - ord('a')] += 1
# p_count：a:1, b:1, c:1
# 初始化第一个窗口 s[0:len(p)]
for i in range(len(p)):
w_count[ord(s[i]) - ord('a') ] += 1
if w_count == p_count:
res.append(0)
#滑动窗口
for i in range(len(p) , len(s)) :
#右边新字符进窗口
w_count[ord(s[i]) - ord('a')] += 1
#左边旧字符出窗口
w_count[ord(s[i-len(p)]) - ord('a')] -= 1
if w_count == p_count:
res.append(i - len(p) + 1 )
return res
# 时间：O(n)，n = len(s)，每个字符进窗口一次、出窗口一次
# 空间：O(1)（26 个字母的常数空间
from collections import Counter
def findAnagrams(s, p):
if len(p) > len(s):
return []
need = Counter(p)
window = Counter()
left = 0
ans = []
for right, ch in enumerate(s):
window[ch] += 1
if right - left + 1 > len(p):
old = s[left]
window[old] -= 1
if window[old] == 0:
del window[old]
left += 1
if window == need:
ans.append(left)
return ans
ACM 训练（输入输出）
输入一行字符串，求无重复字符的最长连续子串长度。
s = input().strip()
seen = set()
left = 0
right = 0
ans = 0
for right in range(lens(s)):
while s[right] in seen :
seen.remove(s[left])
left += 1
seen.add(s[right])
ans = max(ans , right - left +1)
print(ans )
真实机试的时候往往需要自己处理：
input
split
类型转换
输出
面试手撕训练｜LeetCode 739 每日温度
今天要求你练习完整口述。
① 暴力
对每一天向后扫描，找到第一个更高温度，最坏需要 O(n²)。
② 瓶颈
对很多元素重复扫描了相同的后续区间。
③ 优化
我可以维护一个单调递减栈，保存仍然没有找到更高温度的下标。
④ 当前温度更高时
当前温度就是栈顶元素遇到的第一个更高温度，所以不断弹栈并计算下标差。
⑤ 复杂度
每个元素最多入栈和出栈各一次，所以时间 O(n)，额外空间 O(n)。
⑥ 为什么保存下标？
因为题目最终需要计算等待的天数，也就是两个位置的距离。
Day 2 Cheat Sheet
滑动窗口识别信号
看到：
连续
子数组 / 子串
最长 / 最短
至多 K
至少……
窗口内频率
无重复
优先检查滑动窗口。
经典模板：
left = 0
for right in range(len(nums)):
加入 nums[rtight]
while 窗口不合法:
remove nums[left]
left+= 1
update the answer
核心问题始终只有三个：
窗口里维护什么？什么时候扩？什么时候缩？
普通栈识别信号
括号
嵌套
后进先出
撤销
表达式
路径
模板：
stack = []
stack.append(x)
x = stack.pop()
top = stack[-1]
单调栈识别信号
看到：
下一个更大
下一个更小
右边第一个更大
左边第一个更小
最近的……
强烈考虑单调栈。
stack = []
for i, x in enumberate(nums):
while stack and nums[stack[-1]]<x:
j = stack.pop()
# x slove the answer of j
stack.append(i)
今天最容易犯的错误
一看到 for + while 就判断滑动窗口是 O(n²)；要看每个元素实际被访问多少次。
滑动窗口只会背模板，却不知道窗口里到底维护的是 sum、set 还是 frequency。
数组有负数时仍然机械使用“和太大就缩左边”的窗口逻辑。
普通栈和单调栈混淆：单调栈的核心不是 LIFO，而是维护顺序以解决最近更大/更小问题。
单调栈只存值，但题目要求距离时才发现自己需要的是下标。
while stack and … 忘写 stack 判断，直接访问空栈。
觉得单调栈是“神奇模板”，却说不清为什么每个元素最多入栈、出栈一次。
今天真正带走两个判断就够了：
连续区间 + 条件可以通过左右移动维护 → 滑动窗口。
需要找最近/下一个更大或更小元素 → 单调栈。
转载自 CSDN-专业IT技术社区
