滑动窗口最大值（子串-hard）

本文主要是介绍滑动窗口最大值（子串-hard），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

239. 滑动窗口最大值

*困难

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

输入：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       31 [3  -1  -3] 5  3  6  7       31  3 [-1  -3  5] 3  6  7       51  3  -1 [-3  5  3] 6  7       51  3  -1  -3 [5  3  6] 7       61  3  -1  -3  5 [3  6  7]      7

示例 2：

输入：nums = [1], k = 1
输出：[1]

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length

以下是使用双端队列来实现的 Python 代码，时间复杂度为 O(n)，空间复杂度为 O(k)：

from collections import dequeclass Solution:def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:# 结果列表res = []# 双端队列，存储可能的最大值的索引deq = deque()for i in range(len(nums)):# 当队列不为空且当前元素大于队列尾部元素时，弹出队列尾部元素while deq and nums[i] > nums[deq[-1]]:deq.pop()# 添加当前元素索引到队列deq.append(i)# 如果队列头部元素超出窗口范围，弹出队列头部元素if deq[0] == i - k:deq.poll(0)# 当窗口大小达到 k 时，添加队列头部元素（即窗口内最大值）到结果列表if i >= k - 1:res.append(nums[deq[0]])return res

整体思路如下：

我们使用一个双端队列 deq 来存储可能是窗口内最大值的元素索引。
遍历数组 nums ：
- 当队列不为空且当前元素大于队列尾部元素的对应值时，将队列尾部元素弹出，这样能保证队列头部始终是当前窗口内的最大值的索引。
- 将当前元素索引加入队列。
- 检查队列头部元素是否超出了当前窗口范围，如果超出则从队列头部弹出。
- 当遍历到的位置达到窗口大小 k 之后，就将队列头部元素（即当前窗口内的最大值）添加到结果列表中。

这种方法通过巧妙地利用双端队列的特性，能够高效地实时维护窗口内的最大值信息，从而在一次遍历中就得到所有窗口的最大值，达到了较好的时间和空间复杂度。

这篇关于滑动窗口最大值（子串-hard）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！