滑动问题涉及滑动窗口，滑动窗口是一个子列表，操作在一个大数组上，大数组是元素的底层集合。一般用于寻找最有价值的问题。LeetCode第239题：最大滑动窗口题目来自LeetCode上的第239题：最大滑动窗口。题目难度为Hard。给定一个数组nums，有一个大小为k的滑动窗口从数组的最左边移动到数组的最右边。您只能在滑动窗口中看到k个数字。滑动窗口一次只向右移动一位。输入：nums=[1,3,-1,-3,5,3,6,7],andk=3输出：[3,3,5,5,6,7]解释：最大位置滑动窗口值--------------------[13-1]-3536731[3-1-3]5367313[-1-35]367513-1[-353]67513-1-3[536]7613-1-35[367]7看到这个问题，第一反应就是暴力解决。使用两层循环依次查询滑动窗口的最大值。实现代码如下。nums=[1,3,-1,-3,5,3,6,7]k=3res=[]foriinrange(k,len(nums)+1):res.append(max(nums[i-k:i]))print(res)#[3,3,5,5,6,7]但是max的执行效率很低，无法在Leetcode上过关，所以需要继续寻找新的解决方案。双端队列Deque的意思是“双端队列”，即双端队列，具有队列和栈性质的数据结构。顾名思义，它是一个前端和后端都支持插入和删除操作的队列。在Python中，我直接使用列表而不是双端队列，pop(0)表示前端删除操作，pop()表示后端删除操作。双端队列窗口记录元素在滑动窗口中的索引，队列左边界记录当前滑动窗口中最大元素的索引。当队列不为空且左边界出界（滑动窗口向右移动引起）时，更新左边界。当队列不为空时，移除队列中索引对应小于num的元素值，当索引i大于k-1时更新队列，更新输出结果classSolution:defmaxSlidingWindow(self,nums:List[int],k:int)->List[int]:ifnotnums:return[]window,res=[],[]fori,xinenumerate(nums):#如果有窗口和窗口的第一个数不在这个范围内，就出去ifi>=kandwindow[0]<=i-k:window.pop(0)#每次进入窗口都要和上次比较。如果太大，直接删除最后一个whilewindowandnums[window[-1]]<=x:window.pop()#删除最后一个还是不删除一个，必须在window上加上xwindow.append(i)#如果窗口在外面，则将窗口的头部添加到resifi>=k-1:res.append(nums[window[0]])returnresLeetCode问题3无重复字符的最长子串给定一个字符串，请求其长度没有重复字符的最长子串。#例1：#Input:"abcabcbb"#Output:3#Explanation:因为最长的没有重复字符的子串是"abc"，所以它的长度是3#Example2:#Input:"bbbbb"#Output:1#Explanation:因为最长的没有重复字符的子串是“b”，所以它的长度是1。#例3#输入：“pwwkew”#输出：3#解释：因为最长的没有重复字符的子串是“wke”，所以它的长度是3.#请注意你的答案必须是子串的长度，“pwke”是子序列，不是子串。我们来看看“滑动窗口”是如何进行字符串处理的。结合题目中的例子“abcabcbb”字符串，我们来看看如何不重复地找到它的最长子串。首先我们定义窗口的两端：begin和end，分别代表我们要找的子串的开始和结束。开始的时候，begin和end都指向0的位置，也就是'a'，然后end不断向后移动（窗口变宽），当遇到第二个'a'时（遇到重复字符），得到一个子串，它的长度是end和begin位置的差值。如何判断是否遇到了重复字符'a'？需要字典作为辅助数据结构。将end从头开始遇到的每个字符和它的索引位置放入字典中，每次end移动到一个新的字符时检查。一个字典就是classSolution:deflengthOfLongestSubstring(self,s:str)->int:#定义两个变量res和start，res用来存放最长子串的长度，start存放非左边的起始位置-重复子串。'''然后创建哈希表，遍历整个字符串。如果该字符串没有出现在哈希表中，则表示没有遇到该字符。这时候计算最长的不重复子串。当哈希表中的值小于left时，说明left的位置已经更新，需要重新计算最长不重复子串。每次对哈希表中当前字符串对应的赋值加1。:params::return:'''d,res,start={},0,0fori,chinenumerate(s):ifchind:start=max(start,d[ch]+1)res=max(res,i-start+1)d[ch]=ireturnres人生最重要的不是站在哪里，而是心朝向的方向。只要在每篇博文中写下自己的心得体会，修养身心；在每天不断重复的学习中，耐得住寂寞，练出真本事，不惧困难，勇往直前，不忘初心，砥砺前行，人生一定会有所收获，不留遗憾（作者：润森）本文已收录到GitHubhttps://github.com/MaoliRUNsen/runsenlearnpy100
