贪心算法-滑动窗口最大值

 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;
}