leetcode(13)滑动窗口系列题目
3. 无重复字符的最长子串
借助哈希set去重
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
if not s:
return 0
n = len(s)
left = 0
maxL, curL = 0, 0
lookup = set()
for i in range(n):
curL += 1
while s[i] in lookup:
curL -= 1
lookup.remove(s[left])
left += 1
maxL = max(maxL, curL)
lookup.add(s[i])
return maxL
239. 滑动窗口最大值
注意：为了可以同时弹出队首和队尾的元素，我们需要使用双端队列。满足这种单调性的双端队列一般称作「单调队列」。
单调队列真是一种让人感到五味杂陈的数据结构，它的维护过程更是如此.....就拿此题来说，队头最大，往队尾方向单调......有机会站在队头的老大永远心狠手辣，当它从队尾杀进去的时候，如果它发现这里面没一个够自己打的，它会毫无人性地屠城，把原先队里的人头全部丢出去，转身建立起自己的政权，野心勃勃地准备开创一个新的王朝.....这时候，它的人格竟发生了一百八十度大反转，它变成了一位胸怀宽广的慈父！它热情地请那些新来的“小个子”们入住自己的王国......然而，这些小个子似乎天性都是一样的——嫉妒心强，倘若见到比自己还小的居然更早入住王国，它们会心狠手辣地找一个夜晚把它们通通干掉，好让自己享受更大的“蛋糕”；当然，遇到比自己强大的，它们也没辙，乖乖夹起尾巴做人。像这样的暗杀事件每天都在上演，虽然王国里日益笼罩上白色恐怖，但是好在没有后来者强大到足以干翻国王，江山还算能稳住。直到有一天，闯进来了一位真正厉害的角色，就像当年打江山的国王一样，手段狠辣，野心膨胀，于是又是大屠城......历史总是轮回的。
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
que = collections.deque() # 队列中存储的是数值对应的数组下标位置
for i in range(k): # 一轮遍历，先把窗口塞满
while que and nums[i] >= nums[que[-1]]:
que.pop() # 队尾元素较小则删除
que.append(i)
res = [nums[que[0]]] # 将第一个元素，即最大元素返回
for i in range(k,n):
while que and nums[i] >= nums[que[-1]]:
que.pop()
que.append(i)
while que[0] <= i - k: # 判断队首的下标位置是否在当前窗口内
que.popleft()
res.append(nums[que[0]])
return res