LeetCode题目（Python实现）：滑动窗口最大值

一时失言乱红尘 2023-05-28 12:51 115阅读 0赞

### 文章目录 ###

*  题目
 *   *  想法一：利用辅助栈
     *   *  算法实现
         *  执行结果
         *  复杂度分析
     *  双端队列
     *   *  算法实现
         *  执行结果
         *  复杂度分析
     *  动态规划
     *   *  算法实现
         *  执行结果
         *  复杂度分析
     *  双端队列简化版
     *   *  算法实现
         *  执行结果
     *  小结

# 题目 #

给定一个数组 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 <= nums.length <= 10^5
 *  \-10^4 <= nums\[i\] <= 10^4
 *  1 <= k <= nums.length

## 想法一：利用辅助栈 ##

先找一个最简单、最容易实现的想法。

将滑动窗口内的元素加入到辅助栈中，然后移动滑动窗口的同时更新辅助栈，使其元素和滑动窗口内的元素相同，然后取最大值加入到答案列表中。

### 算法实现 ###

def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        slid = nums[:k]
        res = [max(slid)]
        i = k
        n = len(nums)
        while i < n:
            slid.pop(0)
            slid.append(nums[i])
            res.append(max(slid))
            i += 1
        return res

### 执行结果 ###

**执行结果** : 通过  
**执行用时** : 460 ms, 在所有 Python3 提交中击败了30.01%的用户  
**内存消耗** : 17.4 MB, 在所有 Python3 提交中击败了100.00%的用户  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]

### 复杂度分析 ###

*  时间复杂度：O(Nk)。其中 N 为数组中元素个数。
 *  空间复杂度：O(N)

## 双端队列 ##

用双端队列表示滑动窗口，同时保持左端为最大元素索引。

### 算法实现 ###

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):
            # remove indexes of elements not from sliding window
            if deq and deq[0] == i - k:
                deq.popleft()
    
            # remove from deq indexes of all elements
            # which are smaller than current element nums[i]
            while deq and nums[i] > nums[deq[-1]]:
                deq.pop()
    
        # init deque and output
        deq = deque()
        max_idx = 0
        for i in range(k):
            clean_deque(i)
            deq.append(i)
            # compute max in nums[:k]
            if nums[i] > nums[max_idx]:
                max_idx = i
        output = [nums[max_idx]]
    
        # build output
        for i in range(k, n):
            clean_deque(i)
            deq.append(i)
            output.append(nums[deq[0]])
        return output

### 执行结果 ###

![在这里插入图片描述][20200326133843667.png]

### 复杂度分析 ###

*  时间复杂度：O(N)，每个元素被处理两次- 其索引被添加到双向队列中和被双向队列删除。
 *  空间复杂度：O(N)，输出数组使用了 O(N−k+1) 空间，双向队列使用了 O(k)。

## 动态规划 ##

### 算法实现 ###

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

### 执行结果 ###

![在这里插入图片描述][20200326140110548.png]

### 复杂度分析 ###

*  时间复杂度：O(N)，我们对长度为 N 的数组处理了 3次。
 *  空间复杂度：O(N)，用于存储长度为 N 的 left 和 right 数组，以及长度为 N - k + 1的输出数组。

## 双端队列简化版 ##

### 算法实现 ###

def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        deq = deque()
        res = []
        for i in range(len(nums)):
            # 移除队头
            if deq and deq[0] <= i - k:
                deq.popleft()
            # 移除小于当前要加入元素的值的索引
            while deq and nums[i] > nums[deq[-1]]:
                deq.pop()
            # 加入当前索引
            deq.append(i)
            # 更新最大值
            if i >= k - 1:
                res.append(nums[deq[0]])
        return res

### 执行结果 ###

![在这里插入图片描述][20200326135845141.png]

## 小结 ##

题目难度应该为中等，暴力法虽然简单，但是无法达到线性要求，双端队列和动态规划是两种比较难的方法，思路比较重要，这道题没有见过，所以思路比较少，不知道该用什么，以后遇到类似问题思路就会好很多了。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]: /images/20230528/bdc77ab986f34181babce31a7a30cab3.png
[20200326133843667.png]: /images/20230528/3c741262bd1a415094997af1a511cab7.png
[20200326140110548.png]: /images/20230528/ca50a33722fc4bc8ac11bb2fa24a2dc3.png
[20200326135845141.png]: /images/20230528/64ef0f56e2a04545b7f9579c5bbaabaf.png