七十四、滑动窗口最值问题

「@Author：Runsen」

❝

编程的本质来源于算法，而算法的本质来源于数学，编程只不过将数学题进行代码化。「---- Runsen」

❞

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

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，传送门~^[1] ，里面更有大厂面试完整考点，欢迎 Star。

❞

Reference