示例 1:

输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:

输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:

输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。

请注意，你的答案必须是子串的长度，“pwke” 是一个子序列，不是子串。

1.1 解决方案

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        len_s1=0
        max_s1=0
        lookup=set()  #注意set()的用法！
        left=0
        for i in range(len(s)):
            len_s1+=1
            while s[i] in lookup:
                lookup.remove(s[left])
                left+=1
                len_s1-=1
            lookup.add(s[i])
            if max_s1<len_s1:max_s1=len_s1
        return max_s1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

**算法思路：**时间复杂度O(n)

初始化子串的长度len_s1=0、最大不含重复字符的最长子串的长度max_s1=0；设队列lookup=set()，并初始化队首位于字符串的序号left=0
循环for i in range(len(s))：
1. 从字符串左边开始，取s[i]放入队列末尾，len_s1+=1；
2. 用while判断s[i]是否重复？while s[i] in lookup
  1. 如果在，移除队列首的元素lookup.remove(s[left])，左序号右移``left+=1，子串长度减少len_s1-=1`，跳至2.2继续判断；
3. 如果不在，s[i]加入队列末尾lookup.add(s[i]);并判果max_s1<len_s1？，如果是，那么max_s1=len_s1；
返回max_s1。

优化思路：

上述的方法最多需要执行 2n 个步骤。事实上，它可以被进一步优化为仅需要 n 个步骤。我们可以定义字符到索引的映射，而不是使用集合来判断一个字符是否存在。当我们找到重复的字符时，我们可以立即跳过该窗口。

也就是说，如果队列s[i]在[i,j)范围内有与j’重复的字符，我们不需要逐渐增加i。我们可以直接跳过[i,j’]范围内的所有元素，并将i变成j’+1。

2. 滑动窗口最大值

给定一个数组 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
1
2
3
4
5
6
7
8
9
10

提示：

你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。

进阶：

你能在线性时间复杂度内解决此题吗？

2.1 解决方案

1.暴力法

最简单直接的方法是遍历每个滑动窗口，找到每个窗口的最大值。一共有 N - k + 1 个滑动窗口，每个有 k 个元素，于是算法的时间复杂度为 O(Nk)，表现较差。

class Solution:
    def maxSlidingWindow(self, nums: 'List[int]', k: 'int') -> 'List[int]':
        n = len(nums)
        if n * k == 0:
            return []
        
        return [max(nums[i:i + k]) for i in range(n - k + 1)]
1
2
3
4
5
6
7

复杂度分析：

时间复杂度O(kN)：其中 N 为数组中元素个数。
空间复杂度O(N-k+1)：用于输出数组

2.滑动窗口（双端队列）

如何优化时间复杂度呢？首先想到的是使用堆，因为在最大堆中 heap[0] 永远是最大的元素。在大小为 k 的堆中插入一个元素消耗 log(k) 时间，因此算法的时间复杂度为O(Nlog(k))。

那能否得到只要 O(N) 的算法？

我们可以使用双向队列，该数据结构可以从两端以常数时间压入/弹出元素。存储双向队列的索引比存储元素更方便，因为两者都能在数组解析中使用。

算法思路：

处理前 k 个元素，初始化双向队列。
遍历整个数组。在每一步 :

清理双向队列 :
- 只保留当前滑动窗口中有的元素的索引。
- 移除比当前元素小的所有元素，它们不可能是最大的。
将当前元素添加到双向队列中。
将deque[0]添加到输出中。
返回输出数组。

from collections import deque
class Solution:
    def maxSlidingWindow(self, nums: 'List[int]', k: 'int') -> 'List[int]':
        # 基本情况
        n = len(nums)
        if n * k == 0:
            return []
        if k == 1:
            return nums
        
        def clean_deque(i):
            # 从滑动窗口移出元素
            if deq and deq[0] == i - k:  #当窗口有k个元素时，加入元素时要同时从左边移出元素
                deq.popleft()
                
            # 从双端队列中移出比nums[i]小的元素索引
            #目的：方便索引最大值吧？
            while deq and nums[i] > nums[deq[-1]]:
                deq.pop()
        
        # 初始化双端队列：滑动窗口中存放数组的索引！
        deq = deque()
        max_idx = 0
        for i in range(k):
            clean_deque(i)  
            deq.append(i)
            # 计算初始滑动窗口中的最大值
            if nums[i] > nums[max_idx]:
                max_idx = i
        output = [nums[max_idx]]  #初始滑动窗口的最大值
        
        # 滑动该滑动窗口，同时输出最大值
        for i in range(k, n):
            clean_deque(i)          
            deq.append(i)
            output.append(nums[deq[0]])
        return output
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

复杂度分析：

时间复杂度O(N)：每个元素被处理两次——其索引被添加到双向队列中和被双向队列删除。

空间复杂度O(N)：输出数组使用了O(N−k+1) 空间，双向队列使用了O(k)。

3.动态规划

这是另一个 O(N) 的算法。本算法的优点是不需要使用 数组 / 列表 之外的任何数据结构。

算法的思想是将输入数组分割成有 k 个元素的块。若 n % k != 0，则最后一块的元素个数可能更少。

开头元素为 i ，结尾元素为 j 的当前滑动窗口可能在一个块内，也可能在两个块中。

情况 1 比较简单。建立数组 left，其中 left[j] 是从块的开始到下标 j 最大的元素，方向 左->右。

为了处理更复杂的情况 2，我们需要数组 right，其中 right[j] 是从块的结尾到下标 j 最大的元素，方向 右->左。right 数组和 left 除了方向不同以外基本一致。

两数组一起可以提供两个块内元素的全部信息。考虑从下标 i 到下标 j的滑动窗口。根据定义，right[i] 是左侧块内的最大元素， left[j] 是右侧块内的最大元素。因此滑动窗口中的最大元素为 max(right[i], left[j])。

算法思路：

从左到右遍历数组，建立数组 left。
从右到左遍历数组，建立数组 right。
建立输出数组 max(right[i], left[i + k - 1])，其中 i 取值范围为 (0, n - k + 1)。

class Solution:
    def maxSlidingWindow(self, nums: 'List[int]', k: 'int') -> 'List[int]':
        n = len(nums)
      
        if n * k == 0:
            return []
        if k == 1:
            return nums
        
      
        left = [0] * n
        left[0] = nums[0]
        right = [0] * n
        right[n - 1] = nums[n - 1]
      
      
        for i in range(1, n): 
            # from left to right
            if i % k == 0:
                # block start
                left[i] = nums[i]
            else:
                left[i] = max(left[i - 1], nums[i])
                  
            # from right to left
            j = n - i - 1
            if (j + 1) % k == 0:
                # block end
                right[j] = nums[j]
            else:
                right[j] = max(right[j + 1], nums[j])
        
        output = []
        for i in range(n - k + 1):
            output.append(max(left[i + k - 1], right[i]))
            
        return output
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37