做网站网站是什么案件,广州汽车网络推广服务,南宁市建设厅网站,网店美工招聘题目描述
给你一个整数数组 nums#xff0c;有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。 示例 1#xff1a; 输入#xff1a;nums [1,3,-1,-3,5,3,6,7]…题目描述
给你一个整数数组 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 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 示例 2 输入nums [1], k 1 输出[1] 提示 1 nums.length 10^5 -104 nums[i] 10^4 1 k nums.length 以下参考力扣官方题解: 链接https://leetcode.cn/problems/sliding-window-maximum/solutions/543426/hua-dong-chuang-kou-zui-da-zhi-by-leetco-ki6m/ 相关标签
队列、滑动窗口、单调队列、堆优先队列
解题思路
对于每个滑动窗口可以使用 O ( k ) O(k) O(k)的时间遍历每个元素找到最大值。对于长度为 n 的数组 nums窗口的数量为 n-k1因此算法的时间复杂度为 O ( ( n − k 1 ) k ) O ( n k ) O((n-k1)k)O(nk) O((n−k1)k)O(nk)会超出时间限制需要进行一些优化。可以想到对于两个相邻只差一个位置的滑动窗口共用着 k-1 个元素只有一个元素是变化的可以根据这个特点进行优化。
解法1优先队列
对于最大值可以想到一种非常合适的数据结构优先队列堆其中的大根堆可以帮助我们实时维护一系列元素中的最大值。
初始时将数组的前k个元素放入优先队列中。每当向右移动窗口时可以把一个新的元素放入优先队列中此时堆顶的元素就是堆中所有元素的最大值。然而这个最大值可能不在滑动窗口中而是出现在滑动窗口左边界的左侧。因此当我们继续向右移动窗口时这个值就永远不可能出现在滑动窗口中了我们可以将其从优先队列中删除。
我们不断地移除堆顶元素直到其确实出现在滑动窗口中。此时堆顶元素就是滑动窗口中的最大值。为了方便判断堆顶元素和滑动窗口的位置关系我们可以在有限队列中存储二元组 n u m , i n d e x num, index num,index表示元素 num 在数组中的下标为 index。
code
class Solution:def maxSlidingWindow(self, nums:List[int], k:int) - List[int]:n len(nums)# python 默认的优先队列是小根堆q [(-nums[i], i) for i in range(k)]heapq.heapify(q) ans [-q[0][0]]for i in range(k, n):heapq.heappush(q, (-nums[i], i))while q[0][1] i-k:heapq.heappop(q)ans.append(-q[0][0])return ansPython的heapq库是用于实现堆优先队列算法的库。它提供了一些函数来操作堆结构如push、pop、heapify等。
heapq.heapify(q)将列表heap原地转换为一个堆。 heapq.heappush(heap, item将元素item推入堆heap上。 heapq.heappop(q)从堆heap中弹出并返回最小的元素。
复杂度分析
时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)其中n数数组 nums 的长度。在最坏情况下数组的元素单调递增那么最终优先队列中包含了所有元素没有元素被移除。由于将一个元素放入优先队列的时间复杂度为 O ( n ) O(n) O(n)因此总时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)。空间复杂度 O ( n ) O(n) O(n)即优先队列需要使用的空间。这里所有的空间复杂度分析都不考虑返回的答案需要的空间只计算额外的空间使用。
解法2单调队列
由于我们需要求出的是滑动窗口的最大值如果当前的滑动窗口中有两个下标i 和j其中i 在 j的坐标并且i 对应的元素不大于 j 对应的元素。那么当滑动窗口向右移动时只要i 还在窗口中那么j 一定也还在窗口中。因此i对应的元素一定不会是窗口中的最大值了可以将其永久移除。
因此可以使用一个队列存储所有还没有被移除的下标在队列中这些下标按照从小到大的顺序被存储并且在数组nums中对应的值是严格单调递减的。
当窗口向右移动时为了保持队列的性质会不断将新的元素和队尾的元素相比较如果前者大于等于后者那么队尾的元素就可以被永久移除弹出队列。不断进行此操作知道队列为空或新元素小于队尾元素。
由于队列中下标对应的元素是严格单减的因此队首下标对应的元素就是滑动窗口中的最大值。此时最大值可能在窗口左边界的左侧因此还需要不断从队首弹出元素直到队首元素在窗口中。
为了科研同时弹出队首和队尾的元素需要使用双端队列。满足这种单调性的双端队列一般称为单调队列。
class Solution:def maxSlidingWindow(self, nums: List[int], k: int) - List[int]:n len(nums)q collections.deque()for i in range(k):while q and nums[i] nums[q[-1]]:q.pop()q.append(i)ans [nums[q[0]]]for i in range(k, n):while q and nums[i] nums[q[-1]]:q.pop()q.append(i)while q[0] i - k:q.popleft()ans.append(nums[q[0]])return ans复杂度分析
时间复杂度 O ( n ) O(n) O(n)。每个下标恰好被放入队列一次并且最多被弹出队列一次。空间复杂度这里使用的数据结构是双向的因此不断从队首弹出元素保证了队列中最多不会有超过 k1 个元素因此队列使用的空间为 O ( k ) O(k) O(k)。
解法3 分块 预处理
可以将数组nums从左到右按照k个一组进行分组最后一组中元素的数量可能会不足k个。如果希望求出nums[i]到nums[ik-1]的最大值就会有两种情况
如果 i 是 k 的倍数那么 nums[i] 到 nums[ik-1] 恰好是一个分组。只要预处理出每个分组中的最大值即可如果 i 不是 k 的备注那么会跨越两个分组占有第一个分组的后缀以及第二个分组的前缀。假设 j 是 k 的倍数并且 i j jk-1那么 nums[i]~nums[j-1]就是第一个分组的后缀nums[j] 到 nums[ik-1] 就是第二个分组的前缀。如果预处理出每个分组中的前缀最大值和后缀最大值也可以在 O(1) 的时间得到答案。
用 prefixMax [ I ] \textit{prefixMax}[I] prefixMax[I]表示下标 i 对应的分组中以 i 结尾的前缀最大值 suffixMax [ i ] \textit{suffixMax}[i] suffixMax[i] 表示下标 i 对应的分组中以 i 开始的后缀最大值。它们分别满足如下的递推式 prefixMax [ i ] { nums [ i ] , i 是 k 的倍数 max { prefixMax [ i − 1 ] , nums [ i ] } , i 不是 k 的倍数 \textit{prefixMax}[i]\begin{cases} \textit{nums}[i], \quad i ~是~ k ~的倍数 \\ \max\{ \textit{prefixMax}[i-1], \textit{nums}[i] \}, \quad i ~不是~ k ~的倍数 \end{cases} prefixMax[i]{nums[i],max{prefixMax[i−1],nums[i]},i 是 k 的倍数i 不是 k 的倍数
以及 suffixMax [ i ] { nums [ i ] , i 1 是 k 的倍数 max { suffixMax [ i 1 ] , nums [ i ] } , i 1 不是 k 的倍数 \textit{suffixMax}[i]\begin{cases} \textit{nums}[i], \quad i1 ~是~ k ~的倍数 \\ \max\{ \textit{suffixMax}[i1], \textit{nums}[i] \}, \quad i1 ~不是~ k ~的倍数 \end{cases} suffixMax[i]{nums[i],max{suffixMax[i1],nums[i]},i1 是 k 的倍数i1 不是 k 的倍数
需要注意在递推 suffixMax [ i ] \textit{suffixMax}[i] suffixMax[i] 时需要考虑到边界条件 suffixMax [ n − 1 ] nums [ n − 1 ] \textit{suffixMax}[n-1]\textit{nums}[n-1] suffixMax[n−1]nums[n−1]而在递推 prefixMax [ I ] \textit{prefixMax}[I] prefixMax[I] 时的边界条件 prefixMax [ 0 ] nums [ 0 ] \textit{prefixMax}[0]\textit{nums}[0] prefixMax[0]nums[0] 恰好包含在递推式的第一种情况中因此无需特殊考虑。
在预处理完成之后对于 nums [ I ] \textit{nums}[I] nums[I]到 nums [ i k − 1 ] \textit{nums}[ik-1] nums[ik−1] 的所有元素如果 i 不是 k 的倍数那么窗口中的最大值为 suffixMax [ I ] \textit{suffixMax}[I] suffixMax[I] 与 prefixMax [ i k − 1 ] \textit{prefixMax}[ik-1] prefixMax[ik−1] 中的较大值如果 i 是 k 的倍数那么此时窗口恰好对应一整个分组 suffixMax [ I ] \textit{suffixMax}[I] suffixMax[I] 和 prefixMax [ i k − 1 ] \textit{prefixMax}[ik-1] prefixMax[ik−1] 都等于分组中的最大值因此无论窗口属于哪一种情况 suffixMax [ i ] , prefixMax [ i k − 1 ] } \textit{suffixMax}[i], \textit{prefixMax}[ik-1] \big\} suffixMax[i],prefixMax[ik−1]}即为答案。
此方法和稀疏表Sparse Table很类似。
class Solution:def maxSlidingWindow(self, nums: List[int], k: int) - List[int]:n len(nums)prefixMax, suffixMax [0] * n, [0] * nfor i in range(n):if i % k 0:prefixMax[i] nums[i]else:prefixMax[i] max(prefixMax[i - 1], nums[i])for i in range(n - 1, -1, -1):if i n - 1 or (i 1) % k 0:suffixMax[i] nums[i]else:suffixMax[i] max(suffixMax[i 1], nums[i])ans [max(suffixMax[i], prefixMax[i k - 1]) for i in range(n - k 1)]return ans复杂度分析
时间复杂度O(n)空间复杂度存储prefixMax和suffixMax需要的空间。
评论区一个很好的示例
