滑动窗口最小值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 实现#includeiostream#includevector#includequeue#includeutilityusingnamespacestd;vectorintslidingWindowMinimum_heap(constvectorintnums,intk){vectorintresult;if(nums.empty()||k0)returnresult;// 定义最小堆存储 (值, 索引)priority_queuepairint,int,vectorpairint,int,std::greaterpairint,intminHeap;for(inti0;inums.size();i){// 将当前元素加入堆minHeap.emplace(nums[i],i);// 移除堆中不在窗口范围内的元素while(!minHeap.empty()minHeap.top().secondi-k1){minHeap.pop();}// 当窗口形成时记录最小值if(ik-1){result.push_back(minHeap.top().first);}}returnresult;}intmain(){vectorintnums{1,3,-1,-3,5,3,6,7};intk3;vectorintminimaslidingWindowMinimum_heap(nums,k);cout滑动窗口的最小值堆实现: [;for(size_t i0;iminima.size();i){coutminima[i];if(i!minima.size()-1)cout, ;}cout]endl;return0;}输出滑动窗口的最小值堆实现: [-1, -3, -3, -3, 3, 3]2. 使用双端队列Deque思路使用双端队列来维护当前窗口中的候选最小值的索引。队列中存储的索引对应的值是递增的这样队首始终是当前窗口的最小值。当新的元素进入窗口时移除所有比新元素大的元素索引因为它们不再是可能的最小值。时间复杂度O(n)每个元素最多被添加和移除一次。空间复杂度O(k)队列中最多有 k 个元素。C 实现#includeiostream#includevector#includedequeusingnamespacestd;vectorintslidingWindowMinimum_deque(constvectorintnums,intk){vectorintresult;if(nums.empty()||k0)returnresult;dequeintdq;// 存储元素的索引for(inti0;inums.size();i){// 移除队首不在窗口范围内的索引while(!dq.empty()dq.front()i-k1){dq.pop_front();}// 移除队尾所有比当前元素大的索引while(!dq.empty()nums[i]nums[dq.back()]){dq.pop_back();}// 添加当前元素的索引到队尾dq.push_back(i);// 当窗口形成时记录最小值if(ik-1){result.push_back(nums[dq.front()]);}}returnresult;}intmain(){vectorintnums{1,3,-1,-3,5,3,6,7};intk3;vectorintminimaslidingWindowMinimum_deque(nums,k);cout滑动窗口的最小值双端队列实现: [;for(size_t i0;iminima.size();i){coutminima[i];if(i!minima.size()-1)cout, ;}cout]endl;return0;}输出滑动窗口的最小值双端队列实现: [-1, -3, -3, -3, 3, 3]代码解析最小堆实现堆的定义使用priority_queuepairint, int, vectorpairint, int, std::greaterpairint, int定义一个最小堆堆中存储元素的值和对应的索引。遍历数组对于每个元素将其值和索引加入堆。移除所有堆顶的索引不在当前窗口范围内的元素。当窗口形成即i k - 1时将堆顶元素的值即当前窗口的最小值加入结果。时间复杂度每个元素进入堆和可能被移出堆的操作都是 O(log k)因此总体时间复杂度为 O(n log k)。双端队列实现队列的定义使用dequeint存储元素的索引保持队列中的元素对应的值是递增的。遍历数组移除队首不在窗口范围内的索引。移除所有队尾比当前元素大的索引因为这些元素不可能成为未来窗口的最小值。将当前元素的索引添加到队尾。当窗口形成时将队首元素对应的值加入结果。时间复杂度每个元素最多被添加和移除一次因此总体时间复杂度为 O(n)。总结滑动窗口最小值问题可以通过多种方法实现最小堆方法适用于需要频繁查询和动态变化的数据流但时间复杂度较高O(n log k)。双端队列方法更为高效能够在O(n)的时间复杂度内解决问题适用于大规模数据处理。在实际应用中双端队列方法因其高效性通常是首选的解决方案。