求滑动窗口的最小值-育师

滑动窗口最小值（Sliding Window Minimum）是一个常见的算法问题，与滑动窗口最大值类似，广泛应用于数据流分析、信号处理等领域。本文将介绍滑动窗口最小值的定义、常见解法以及使用堆和双端队列（Deque）实现的C++代码。

问题描述

给定一个整数数组nums和一个滑动窗口大小k，请你找出所有滑动窗口中的最小值。

示例：

输入: nums = [1,3,-1,-3,5,3,6,7], k = 3 输出: [ -1, -3, -3, -3, 3, 3]

解释:
滑动窗口的位置及其最小值分别为：

窗口位置 最小值 --------------- ----- [1 3 -1] -3 5 3 6 7 -1 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 -3 1 3 -1 -3 [5 3 6] 7 3 1 3 -1 -3 5 [3 6 7] 3

解法

1. 使用最小堆（Min-Heap）

思路：

使用一个最小堆来维护当前窗口中的元素。堆中存储元素的值和对应的索引。每次滑动窗口时，移除堆中不在窗口范围内的元素，然后堆顶即为当前窗口的最小值。

时间复杂度：O(n log k)，其中 n 是数组长度，k 是窗口大小。

空间复杂度：O(k)，堆中最多有 k 个元素。

C++ 实现：

#include<iostream>#include<vector>#include<queue>#include<utility>usingnamespacestd;vector<int>slidingWindowMinimum_heap(constvector<int>&nums,intk){vector<int>result;if(nums.empty()||k<=0)returnresult;// 定义最小堆，存储 (值, 索引)priority_queue<pair<int,int>,vector<pair<int,int>>,std::greater<pair<int,int>>>minHeap;for(inti=0;i<nums.size();++i){// 将当前元素加入堆minHeap.emplace(nums[i],i);// 移除堆中不在窗口范围内的元素while(!minHeap.empty()&&minHeap.top().second<i-k+1){minHeap.pop();}// 当窗口形成时，记录最小值if(i>=k-1){result.push_back(minHeap.top().first);}}returnresult;}intmain(){vector<int>nums={1,3,-1,-3,5,3,6,7};intk=3;vector<int>minima=slidingWindowMinimum_heap(nums,k);cout<<"滑动窗口的最小值（堆实现）: [";for(size_t i=0;i<minima.size();++i){cout<<minima[i];if(i!=minima.size()-1)cout<<", ";}cout<<"]"<<endl;return0;}

输出：

滑动窗口的最小值（堆实现）: [-1, -3, -3, -3, 3, 3]

2. 使用双端队列（Deque）

思路：

使用双端队列来维护当前窗口中的候选最小值的索引。队列中存储的索引对应的值是递增的，这样队首始终是当前窗口的最小值。当新的元素进入窗口时，移除所有比新元素大的元素索引，因为它们不再是可能的最小值。

时间复杂度：O(n)，每个元素最多被添加和移除一次。

空间复杂度：O(k)，队列中最多有 k 个元素。

C++ 实现：

#include<iostream>#include<vector>#include<deque>usingnamespacestd;vector<int>slidingWindowMinimum_deque(constvector<int>&nums,intk){vector<int>result;if(nums.empty()||k<=0)returnresult;deque<int>dq;// 存储元素的索引for(inti=0;i<nums.size();++i){// 移除队首不在窗口范围内的索引while(!dq.empty()&&dq.front()<i-k+1){dq.pop_front();}// 移除队尾所有比当前元素大的索引while(!dq.empty()&&nums[i]<=nums[dq.back()]){dq.pop_back();}// 添加当前元素的索引到队尾dq.push_back(i);// 当窗口形成时，记录最小值if(i>=k-1){result.push_back(nums[dq.front()]);}}returnresult;}intmain(){vector<int>nums={1,3,-1,-3,5,3,6,7};intk=3;vector<int>minima=slidingWindowMinimum_deque(nums,k);cout<<"滑动窗口的最小值（双端队列实现）: [";for(size_t i=0;i<minima.size();++i){cout<<minima[i];if(i!=minima.size()-1)cout<<", ";}cout<<"]"<<endl;return0;}

输出：

滑动窗口的最小值（双端队列实现）: [-1, -3, -3, -3, 3, 3]

代码解析

最小堆实现

堆的定义：
- 使用priority_queue<pair<int, int>, vector<pair<int, int>>, std::greater<pair<int, int>>>定义一个最小堆，堆中存储元素的值和对应的索引。
遍历数组：
- 对于每个元素，将其值和索引加入堆。
- 移除所有堆顶的索引不在当前窗口范围内的元素。
- 当窗口形成（即i >= k - 1）时，将堆顶元素的值（即当前窗口的最小值）加入结果。
时间复杂度：
- 每个元素进入堆和可能被移出堆的操作都是 O(log k)，因此总体时间复杂度为 O(n log k)。

双端队列实现

队列的定义：
- 使用deque<int>存储元素的索引，保持队列中的元素对应的值是递增的。
遍历数组：
- 移除队首不在窗口范围内的索引。
- 移除所有队尾比当前元素大的索引，因为这些元素不可能成为未来窗口的最小值。
- 将当前元素的索引添加到队尾。
- 当窗口形成时，将队首元素对应的值加入结果。
时间复杂度：
- 每个元素最多被添加和移除一次，因此总体时间复杂度为 O(n)。