leetcode239：滑动窗口最大值

题目链接

leetcode

题目描述

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值 。

C++ 代码

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#include <iostream>
#include <deque>
#include <vector>
#include <queue>
using namespace std;

void printArray(const vector<int>& nums) {
    cout << "[";
    for (const int& num : nums) {
        cout << num << ",";
    }
    cout << "]";
}

/*
    优先队列：大根堆实时维护一系列元素中的最大值。

    初始时，将数组 nums 的前 k 个元素放入优先队列。
    每次向右移动窗口时，将一个新的元素放入队列，此时堆顶的元素就是堆中所有元素的最大值。
    不断地移除堆顶的元素，直到其出现在滑动窗口中。此时，堆顶元素就是滑动窗口中的最大值。

    时间复杂度：O(nlogk)
        其中 n 是输入数组的长度，k 是窗口的大小。
        在每次循环中，插入和删除元素的时间复杂度都是 O(logk)，因此总的时间复杂度为 O(nlogk)。
    空间复杂度：O(k)
        k 是窗口的大小，存储最大堆。
        不考虑返回答案需要的 O(n) 空间，只计算额外的空间使用。
*/
class Solution_0 {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        priority_queue<pair<int, int>> q;
        for (int i = 0; i < k; i ++) {
            q.emplace(nums[i], i);
        }

        vector<int> res = { q.top().first };
        for (int i = k; i < n; i ++) {
            q.emplace(nums[i], i);
            while (q.top().second <= i - k) {
                q.pop();
            }
            res.push_back(q.top().first);
        }
        
        return res;
    }
};

/*
    滑动窗口

    使用双向队列：
        为了同时弹出队首和队尾的元素，使用双端队列。
        双向队列用来存储可能成为窗口最大值的元素下标。
        队列的头部始终是当前窗口的最大值。
    维护队列：
        遍历数组，不断地更新队列，确保队列中的元素从大到小排列。
    处理窗口滑动：
        当窗口向前滑动时，移除不在窗口内的元素，并添加新进入窗口的元素。
    
    时间复杂度：O(n)
        其中 n 是数组 nums 的长度，每个元素最多被加入和移除队列一次。
    空间复杂度：O(k)
        与方法一不同的是，在方法二中使用的数据结构是双向的。
        不断从队首弹出元素，保证了队列中最多不超过 k 个元素。
*/
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        deque<int> q;
        for (int i = 0; i < k; i ++) {
            // 窗口内填满 k 个元素
            while (!q.empty() && nums[i] >= nums[q.back()]) {
                q.pop_back();
            }
            q.push_back(i);
        }
        vector<int> res = { nums[q.front()] };
        for (int i = k; i < n; i ++) {
            // 窗口向前滑动，加入新数字
            while (!q.empty() && nums[i] >= nums[q.back()]) {
                q.pop_back();
            }
            q.push_back(i);
            // 移出旧数字
            while (q.front() <= i - k) {
                q.pop_front();
            }
            // 保存当前窗口的最大值
            res.push_back(nums[q.front()]);
        }

        return res;
    }
};

/*
    思路同上
*/
class Solution_2 {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        MonotonicQueue window;
        
        for (int i = 0; i < nums.size(); i ++) {
            if (i < k - 1) {
                // 填满窗口的前 k - 1
                window.push(nums[i]);
            } else {
                // 窗口向前滑动，加入新数字
                window.push(nums[i]);
                // 保存当前窗口的最大值
                res.push_back(window.max());
                // 移出旧数字
                window.pop(nums[i - k + 1]);
            }
        }

        return res;
    }

private:
    class MonotonicQueue {
    private:
        deque<int> q;
    public:
        void push(int n) {
            // 将小于 n 的元素全部删除
            while (!q.empty() && q.back() < n) {
                q.pop_back();
            }
            // 将 n 加入尾部
            q.push_back(n);
        }

        void pop(int n) {
            if (q.front() == n) {
                q.pop_front();
            }
        }

        int max() {
            return q.front();
        }
    };
};

int main() {
    Solution solution;
    vector<vector<int>> nums = { 
        {1,3,-1,-3,5,3,6,7},
        {1}
    };
    vector<int> k_nums = { 3, 1 };

    for (int i = 0; i < nums.size(); i ++) {
        cout << "Input: ";
        printArray(nums[i]);
        cout << ", k: " << k_nums[i] << endl;
        vector<int> res = solution.maxSlidingWindow(nums[i], k_nums[i]);
        cout << "Output: ";
        printArray(res);
        cout << endl;
    }
    
    return 0;
}

Golang 代码

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
package main

import (
	"container/heap"
	"fmt"
)

/*
   基本思路是：
       创建一个最大堆和一个结果切片。
       遍历输入数组，对于每个元素：
           将当前元素加入最大堆。
           若最大堆的大小超过了窗口大小，则移除堆顶元素。
           若窗口已形成，则将堆顶元素加入结果切片。
       返回结果切片。

   时间复杂度：O(nlogk)
       其中 n 是输入数组的长度，k 是窗口的大小。
       在每次循环中，插入和删除元素的时间复杂度都是 O(logk)，因此总的时间复杂度为 O(nlogk)。
   空间复杂度：O(k)
       k 是窗口的大小，用于存储最大堆。
*/
func maxSlidingWindow_0(nums []int, k int) []int {
    if len(nums) == 0 || k == 0 {
		return []int{}
	}

    // 初始化最大堆
	maxHeap := &MaxHeap{nums: make([]int, 0), vals: nums}
	heap.Init(maxHeap)
    // 初始化结果
	res := make([]int, 0)

    // 初始化窗口
	for i := 0; i < k; i++ {
		heap.Push(maxHeap, i)
	}
    res = append(res, nums[maxHeap.Peek()])
    // 滑动窗口
	for i := k; i < len(nums); i++ {
        heap.Push(maxHeap, i)
		// 移除窗口外的元素
		for maxHeap.Peek() <= i - k {
			heap.Pop(maxHeap)
		}
		res = append(res, nums[maxHeap.Peek()])
	}

	return res
}

// 定义一个最大堆类型
type MaxHeap struct {
	nums []int // 存储索引
	vals []int // 存储值
}

// 实现 heap.Interface 的方法
func (h MaxHeap) Len() int {
	return len(h.nums)
}

// Less 方法定义了优先队列中元素的比较规则，这里希望最大的元素在队列的前面
func (h MaxHeap) Less(i, j int) bool {
	return h.vals[h.nums[i]] > h.vals[h.nums[j]] // 最大堆
}

// Swap 方法交换堆中的两个元素
func (h MaxHeap) Swap(i, j int) {
	h.nums[i], h.nums[j] = h.nums[j], h.nums[i]
}

// Push 方法将一个新元素推入堆中
func (h *MaxHeap) Push(x interface{}) {
	idx := x.(int)
	h.nums = append(h.nums, idx)
}

// Pop 方法从堆中弹出一个元素
func (h *MaxHeap) Pop() interface{} {
	old := h.nums
	n := len(old)
	x := old[n-1]
	h.nums = old[:n-1]
	return x
}

// 获取堆顶元素的值
func (h MaxHeap) Peek() int {
	return h.nums[0]
}

/*
    基本思路是：
        使用一个双向队列来维护滑动窗口内的元素索引。
        通过遍历数组，将当前元素的索引加入队列，并从队尾移除小于当前元素的索引。
        若队头的索引超出了窗口范围，则将其移除。
        当窗口形成时，将队头的元素加入结果切片。

    时间复杂度：O(n)
        其中 n 是数组 nums 的长度。
        每一个下标恰好被放入队列一次，并且最多被弹出队列一次。
    空间复杂度：O(k)
        k 是窗口的大小，用于存储最大堆。
*/
func maxSlidingWindow(nums []int, k int) []int {
    if len(nums) == 0 || k == 0 {
		return []int{}
	}

    // 创建一个结果切片，存储每个滑动窗口的最大值
    res := make([]int, 0)
    // 创建一个双向队列，存储窗口内的元素索引
    deque := make([]int, 0)

    for i := 0; i < len(nums); i ++ {
        // 从队尾移除小于当前元素的索引
        for len(deque) > 0 && nums[deque[len(deque) - 1]] < nums[i] {
            deque = deque[:len(deque) - 1]
        }
        // 将当前元素的索引加入队尾
        deque = append(deque, i)
        // 若队头的索引超出窗口范围，则将其移除
        if deque[0] <= i - k {
            deque = deque[1:]
        }
        // 若窗口已经形成，则将队头的元素加入结果中
        if i >= k - 1 {
            res = append(res, nums[deque[0]])
        }
    }

    return res
}

/*
    思路同上
*/
func maxSlidingWindow_2(nums []int, k int) []int {
    if len(nums) == 0 || k == 0 {
		return []int{}
	}

    // 创建一个结果切片，存储每个滑动窗口的最大值
    res := make([]int, 0)
    // 创建一个单调队列（双向的），存储窗口内的元素索引
    window := MonotonicQueue{make([]int, 0)}

    for i := 0; i < len(nums); i ++ {
        if i < k - 1 {
            // 填满窗口的前 k - 1
            window.push(nums[i])
        } else {
            // 窗口向前滑动，加入新数字
            window.push(nums[i])
            // 保存当前窗口的最大值
            res = append(res, window.max())
            // 移出旧数字
            window.pop(nums[i - k + 1])
        }
    }

    return res
}

// MonotonicQueue 单调队列
type MonotonicQueue struct {
    q []int
}

// push 将元素 n 加入队列
func (mq * MonotonicQueue) push(n int) {
    // 将小于 n 的元素全部删除
    for len(mq.q) > 0 && mq.q[len(mq.q) - 1] < n {
        mq.q = mq.q[:len(mq.q) - 1]
    }
    // 将 n 加入尾部
    mq.q = append(mq.q, n)
}

// pop 移出队列中的元素 n
func (mq *MonotonicQueue) pop(n int) {
    if n == mq.q[0] {
        mq.q = mq.q[1:]
    }
}

// max 返回队列的最大值
func (mq *MonotonicQueue) max() int {
    return mq.q[0]
}

func main() {
    // 测试用例
	testCases := []struct {
		nums     []int
		k        int
		expected []int
	}{
        {[]int{1,3,-1,-3,5,3,6,7}, 3, []int{3,3,5,5,6,7}},
        {[]int{1}, 1, []int{1}},
	}

	for i, tc := range testCases {
		result := maxSlidingWindow(tc.nums, tc.k)
		fmt.Printf("Test Case %d, Input: nums = %v, k = %d\n", i+1, tc.nums, tc.k)
        resultStr := fmt.Sprintf("%v", result)
        expectedStr := fmt.Sprintf("%v", tc.expected)

		if resultStr == expectedStr {
			fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, resultStr)
		} else {
			fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, resultStr, expectedStr)
		}
	}
}
#leetcode
leetcode239：滑动窗口最大值
https://lcf163.github.io/2024/05/02/leetcode239：滑动窗口最大值/
作者
乘风的小站
发布于
2024年5月2日
许可协议