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

输入: 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]

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

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

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