单调队列的两种思路：强单调和弱单调
共同点是都关注队列首位是最大的。
不同点在于（假设窗口大小为3）：
- 弱单调只要首位最大，一个元素如果保持最大返回3次，那必然满了（队列长度到3了）。所以满了就是返回了3次的情况，这时候pop掉首位。
但弱单调去掉首位，剩下的不一定弱单调，所以还需要维护剩下的成为弱单调(625->25，不单调了) - 强单调是严格单调，队列满了，则必然已经返回3次了，但返回3次不一定会满（比如6，62，625->65，这在弱单调里就满了）。但好在返回3次是有解法的，即和num(i-3)比较。这就是强单调的好处（在写法上不需要维护单调性）。
但两种的复杂度是没有多大区别的，别看写法上强单调for循环内只有一个while，弱单调for循环内有两个while。
- 强单调在进入队列的时候是和s[-1]比较的，也就是说从最小的比到最大的，多次比较。
而弱单调则只比较一次，和最大的比，如果要出队列，则全出，直接一次赋值[]即可 - 强单调在处理满了或已返回3次的情况，就方便了，只需要一次pop。
而弱单调之前入栈很方便，但积累了“弱性”/“不严格单调性”，在处理满了的情况，就爆发了，在这需要多次比较的pop，以维护一个弱单调性队列(625->25->5)
所以这两种方法的本质不同在于，对元素出入队列的处理的方式/时机的不同，而不影响复杂度。
从每个元素本身考虑，最多出入队列各一次，遍历所有队列，所以时间复杂度不超过O(2n)。
- 弱单调 （如[6,2]将5进入队列后变成[6, 2, 5]，只要首位最大）
class Solution:
def maxInWindows(self , num: List[int], size: int) -> List[int]:
if size > len(num) or not size : return None
if size == len(num): return [max(num)]
if size == 1: return num
# 两个列表一个存储结果，一个作弱单调队列，只保存从大到小的结果
res, s = [], []
# 未形成窗口期：先把头 size-1 个数存入单调队列中。
for i in range(size - 1):
if not s:
s.append(num[i])
else:
# 都是和s[0]比较，所以是弱单调
# 小的直接入队，大的则要先出队，再判断直到小的或者空的，才入队
while len(s) and s[0] <= num[i]:
s = []
s.append(num[i])
# 形成窗口期：循环后len-(size-1)个数，，每轮循环都存结果到res里面
for i in range(size - 1, len(num)):
# 满了的情况，先出队。出队后不一定弱单调添加一轮循环，去掉不符合顺序的
if len(s) == size:
s.pop(0)
j = 0
while len(s) > 1 and j <= len(s) - 2 and s[0] <= s[1]:
s.pop(0)
# 维护弱单调队列
while len(s) and s[0] <= num[i]:
s = []
s.append(num[i])
# 每轮返回s[0]
res.append(s[0])
return res- 强单调（没有[6, 2, 5]，只会退化为[6, 5]，严格递减）
class Solution:
def maxInWindows(self , num: List[int], size: int) -> List[int]:
if size > len(num) or not size : return None
if size == len(num): return [max(num)]
if size == 1: return num
res, s = [], []
for i in range(size - 1):
if not s:
s.append(num[i])
else:
# 和s[-1]比较，所以是强单调，严格递减。
while len(s) and s[-1] <= num[i]:
s.pop()
s.append(num[i])
for i in range(size - 1, len(num)):
if s[0] == num[i - size]:
s.pop(0)
while len(s) and s[-1] <= num[i]:
s.pop()
s.append(num[i])
res.append(s[0])
return res
京公网安备 11010502036488号