详解滑动窗口最值问题

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

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 )

本文已收录 GitHub  https://github.com/MaoliRUNsen/runsenlearnpy100