滑动问题包含一个滑动窗口，它是一个运行在一个大数组上的子列表，该数组是一个底层元素集合。一般用来求最值问题。

LeetCode 第 239 题：滑动窗口最大值

题目来源于 LeetCode 上第 239 号问题：滑动窗口最大值。题目难度为 Hard 。

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 
输出: [3,3,5,5,6,7]  
解释:  
 
  滑动窗口的位置                最大值 
---------------                ----- 
[1  3  -1] -3  5  3  6  7       3 
 1 [3  -1  -3] 5  3  6  7       3 
 1  3 [-1  -3  5] 3  6  7       5 
 1  3  -1 [-3  5  3] 6  7       5 
 1  3  -1  -3 [5  3  6] 7       6 
 1  3  -1  -3  5 [3  6  7]      7

看到这个题之后，第一直觉就是暴力解法，用两层循环依次查询滑动窗口的最大值，实现代码如下。

nums = [1, 3, -1, -3, 5, 3, 6, 7] 
k = 3 
res = [] 
for i in range(k, len(nums) + 1): 
    res.append(max(nums[i - k:i])) 
print(res)  #[3, 3, 5, 5, 6, 7]

但max执行效率却很低，在Leetcode上不能通过，因此我们需要继续找寻新的解决方案。

双端队列

Deque 的含义是 “double ended queue”，即双端队列，它具有队列和栈的性质的数据结构。顾名思义，它是一种前端与后端都支持插入和删除操作的队列。

在Python中，我直接使用列表代替双端队列，pop(0)表示前端删除操作，pop()表示后端删除操作。

双端队列window记录滑动窗口中元素的索引，队列左边界记录当前滑动窗口中最大元素的索引

• 当队列非空，左边界出界时(滑动窗口向右移导致的)，更新左边界

• 当队列非空，将队列中索引对应的元素值比 num 小的移除，更新队列

• 当索引 i 大于 k-1，更新输出结果

class Solution: 
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: 
        if not  nums: return [] 
        window ,res = [],[] 
        for i,x in enumerate(nums): 
            # 如果存在窗口 而且窗口的第一个数 不在这个范围，就出去 
            if i >= k and window[0] <= i-k: 
                window.pop(0) 
            # 每次进入窗口的和最后一个比较，如果大了，最后一个直接删除 
            while window and nums[window[-1]] <= x: 
                window.pop() 
            # 无论是不是删除最后一个，都要加入x到窗口中 
            window.append(i) 
            # 如果出了窗口，就把窗口的头加入到res中 
            if i >= k-1: 
                res.append(nums[window[0]]) 
        return res

LeetCode 第 3 题 无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

# 示例 1: 
# 输入: "abcabcbb" 
# 输出: 3 
#解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 
# 示例 2: 
# 输入: "bbbbb" 
#输出: 1 
#解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 
# 示例 3 
# 输入: "pwwkew" 
#输出: 3 
#解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 
#请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

下面我们看看，“滑动窗口”如何进行字符串处理。结合题目中的例子“abcabcbb”这个字符串，我们来看看如何找它的无重复最长子串。

首先，我们定义窗口的两端：begin和end，分别表示要找的子串的开头和结尾。

开始的时候，begin和end都指向0的位置即‘a’，然后end不断后移(窗口变宽)，当遇到第二个‘a’时(遇见重复字符)就得到一个子串，其长度就是end和begin位置的差。

如何判断是否遇到了重复字符‘a’呢?需要一个字典作为辅助数据结构，把end从头开始遇到的每个字符及其索引位置都放到字典里面，end每次移动到新字符就查一下字典即可

class Solution: 
    def lengthOfLongestSubstring(self, s: str) -> int: 
        # 定义两个变量res和start,res用于存储最长子字符串的长度，start存储无重复子串左边的起始位置。 
        ''' 
        然后创建一个哈希表，遍历整个字符串，如果字符串没有在哈希表中出现，说明没有遇到过该字符，则此时计算最长无重复子串，当哈希表中的值小于left，说明left位置更新了，需要重新计算最长无重复子串。每次在哈希表中将当前字符串对应的赋值加1。 
        :param s: 
        :return: 
        ''' 
        d, res, start = {}, 0, 0 
        for i, ch in enumerate(s): 
            if ch in d: 
                start = max(start, d[ch] + 1) 
            res = max(res, i - start + 1) 
            d[ch] = i 
        return res

人生最重要的不是所站的位置，而是内心所朝的方向。只要我在每篇博文中写得自己体会，修炼身心;在每天的不断重复学习中，耐住寂寞，练就真功，不畏艰难，奋勇前行，不忘初心，砥砺前行，人生定会有所收获，不留遗憾 (作者：Runsen )