栈

表达式解析是栈的看家副本：数字栈、符号栈、递归下降，三件套凑齐就能通关四则运算全系列。本合集收录栈类题目。

表达式解析

leetcode 1006

中缀表达式求值一般要维护数字、操作符两个栈；这题操作符顺序是固定循环的，可以省掉操作符栈，只留一个数字栈：乘除和栈顶连着算，加号把数正着入栈，减号把数取负入栈，最后求和。需要注意负数除法的取整方向：题目里的数都是正数，但减号后的那段乘积以负数入栈后再做除法，Python 的 // 向下取整（-42 // 5 == -9），而这里要的是先算正数的商再取负（-8），得写成 int(a / b) 或对绝对值做除法。

leetcode 394

可...

Read more

滑动窗口和双指针

双指针的精髓在于「不回头」：每个元素只被指针扫过常数次，$O(n^2)$ 的枚举就塌缩成 $O(n)$。本合集收录滑动窗口与双指针题目。

分组循环

同向双指针的一种特殊形态：左端点 start 只在每组开头记一次，右端点就是循环变量 i 本身，组与组之间不回退。

适用场景

数组会被切成若干组，每一组的处理逻辑相同。

核心思想

外层循环负责进组前的准备（记录起点）和出组后的统计（更新答案）；内层循环负责走完这一组，找出它最远在哪结束。

模板

n = len(nums)
i = 0
while i < n:
    start = i
    i += 1  # a gro...

Read more