有一个长为 n 的序列 𝑎,以及一个大小为 k 的窗口。现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值。
例如,对于序列 [1,3,−1,−3,5,3,6,7] 以及 k=3
其滑动窗口最大值为3 3 5 5 6 7
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | /**************************************************************** * Description: 用单调队列计算滑动窗口最大值 * Author: Alex Li * Date: 2024-06-24 14:29:38 * LastEditTime: 2024-06-24 15:19:11 ****************************************************************/ #include <iostream> #include <vector> #include <deque> using namespace std; vector<int> maxSlidingWindow(vector<int>& nums, int k) { vector<int> result; deque<int> deq; for (int i = 0; i < nums.size(); ++i) { // Remove elements not within the sliding window if (!deq.empty() && deq.front() < i - k + 1) { deq.pop_front(); } // Maintain elements in decreasing order while (!deq.empty() && nums[deq.back()] < nums[i]) { deq.pop_back(); } // Add current element's index deq.push_back(i); // Append the current maximum to the result if (i >= k - 1) { result.push_back(nums[deq.front()]); } } return result; } int main() { vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7}; int k = 3; vector<int> result = maxSlidingWindow(nums, k); for (int num : result) cout << num << " "; return 0; } |
洛谷:P1886