滑动窗口最大值
题目要求
给定一个整数数组nums和一个正整数k，定义一个大小为k的滑动窗口，该窗口从数组的最左侧开始，每次向右移动一个元素，直至到达数组的最右侧。在每个窗口位置，需要找出窗口内的最大值。
要求编写一个算法，计算并返回一个数组，该数组中的每个元素代表了每次滑动窗口移动后窗口内的最大值。
解题思路
解决这个问题的关键是如何高效地从每个窗口中找到最大值。直观的方法是对每个窗口内的元素进行比较，但这样的时间复杂度较高。为了优化性能，可以采用以下策略：
-
双端队列（Deque）：使用一个双端队列来存储窗口内的元素的索引，并保持队列内的元素索引对应的
nums中的值是非递增的。这样，队列的头部始终是当前窗口内最大值的索引。- 当窗口向右移动时，首先检查队列头部的索引是否已经超出了窗口的范围（即头部索引小于当前索引减去窗口大小
k），如果是，则将其从队列中移除。 - 然后，从队列尾部开始，移除所有小于当前元素值的索引，因为这些元素不可能是当前窗口或之后窗口的最大值。
- 将当前元素的索引添加到队列尾部。
- 队列头部的索引对应的
nums中的值即为当前窗口的最大值。
- 当窗口向右移动时，首先检查队列头部的索引是否已经超出了窗口的范围（即头部索引小于当前索引减去窗口大小
-
窗口初始化：初始化时，先填充满第一个窗口的双端队列。
-
滑动窗口：从
k开始遍历数组，每次移动窗口时，更新双端队列，并从队列头部获取最大值。 -
结果输出：按照窗口移动的顺序，将每次得到的最大值存入结果数组。
通过上述方法，可以将问题的时间复杂度从O(nk)降低到O(n)，其中n是数组nums的长度，因为每个元素最多被加入和移除队列一次。
Golang 版本
package main
import "fmt"
// 使用双端队列来存储索引
type Deque []int
// PushBack 在队列尾部添加元素
func (dq *Deque) PushBack(value int) {
*dq = append(*dq, value)
}
// PopFront 从队列头部移除元素
func (dq *Deque) PopFront() {
*dq = (*dq)[1:]
}
// PopBack 从队列尾部移除元素
func (dq *Deque) PopBack() {
*dq = (*dq)[:len(*dq)-1]
}
// Front 获取队列头部元素
func (dq *Deque) Front() int {
return (*dq)[0]
}
// Back 获取队列尾部元素
func (dq *Deque) Back() int {
return (*dq)[len(*dq)-1]
}
// MaxSlidingWindow 返回滑动窗口中的最大值
func MaxSlidingWindow(nums []int, k int) []int {
var result []int
var window Deque
for i, x := range nums {
// 移除所有小于当前元素值的索引
for len(window) > 0 && nums[window.Back()] <= x {
window.PopBack()
}
// 添加当前元素索引
window.PushBack(i)
// 确保队列头部的索引在窗口内
if window.Front() == i-k {
window.PopFront()
}
// 当窗口大小为k时，记录当前窗口的最大值
if i >= k-1 {
result = append(result, nums[window.Front()])
}
}
return result
}
func main() {
nums := []int{1, 3, -1, -3, 5, 3, 6, 7}
k := 3
fmt.Println(MaxSlidingWindow(nums, k))
}
这段代码实现了一个双端队列，并使用它来解决滑动窗口最大值的问题。在main函数中，我们定义了一个示例数组nums和窗口大小k，然后调用MaxSlidingWindow函数并打印结果。
C++版本
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> window; // 双端队列，用于存储索引
vector<int> max_values; // 存储每个窗口的最大值
for (int i = 0; i < nums.size(); ++i) {
// 移除所有小于当前元素值的索引
while (!window.empty() && nums[i] >= nums[window.back()]) {
window.pop_back();
}
// 添加当前元素索引
window.push_back(i);
// 确保队列头部的索引在窗口内
if (window.front() == i - k) {
window.pop_front();
}
// 当窗口大小为k时，记录当前窗口的最大值
if (i >= k - 1) {
max_values.push_back(nums[window.front()]);
}
}
return max_values;
}
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 << " ";
}
cout << endl;
return 0;
}
这段 C++代码定义了一个maxSlidingWindow函数，它接受一个整数数组nums和一个整数k作为参数，并返回一个包含每个滑动窗口最大值的整数数组。在main函数中，我们创建了一个示例数组和窗口大小，调用了maxSlidingWindow函数，并打印了结果。
Python 版本
from collections import deque
def max_sliding_window(nums, k):
if not nums:
return []
window = deque()
max_values = []
for i, value in enumerate(nums):
# 移除所有小于当前元素值的索引
while window and nums[window[-1]] < value:
window.pop()
window.append(i)
# 移除不在滑动窗口内的元素的索引
if window[0] == i - k:
window.popleft()
# 当窗口大小为k时，记录当前窗口的最大值
if i >= k - 1:
max_values.append(nums[window[0]])
return max_values
# 示例
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(max_sliding_window(nums, k))
这段 Python 代码实现了一个max_sliding_window函数，它接受一个整数列表nums和一个整数k作为参数，并返回一个列表，其中包含每个滑动窗口的最大值。代码中使用了collections.deque来高效地处理窗口内的索引。在示例调用中，我们定义了一个数组和窗口大小，然后打印了函数的返回值。
Java 版本
import java.util.ArrayDeque;
import java.util.Deque;
public class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || k <= 0) {
return new int[0];
}
int n = nums.length;
int[] result = new int[n - k + 1]; // 数组长度为 n - k + 1
int ri = 0; // 结果数组的索引
Deque<Integer> q = new ArrayDeque<>(); // 双端队列，用于存储索引
for (int i = 0; i < nums.length; i++) {
// 移除不在滑动窗口内的元素的索引
while (!q.isEmpty() && q.peek() < i - k + 1) {
q.poll();
}
// 移除所有小于当前元素值的索引
while (!q.isEmpty() && nums[q.peekLast()] < nums[i]) {
q.pollLast();
}
// 添加当前元素索引
q.offer(i);
// 当窗口大小为k时，记录当前窗口的最大值
if (i >= k - 1) {
result[ri++] = nums[q.peek()];
}
}
return result;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
int[] result = solution.maxSlidingWindow(nums, k);
for (int num : result) {
System.out.print(num + " ");
}
}
}
这段 Java 代码定义了一个Solution类，其中包含了maxSlidingWindow方法，该方法接受一个整数数组nums和一个整数k作为参数，并返回一个数组，其中包含每个滑动窗口的最大值。在main方法中，我们创建了一个Solution对象，定义了一个示例数组和窗口大小，调用了maxSlidingWindow方法，并打印了结果。
Rust 版本
use std::collections::VecDeque; pub fn max_sliding_window(nums: Vec<i32>, k: usize) -> Vec<i32> { let mut result = Vec::new(); let mut deque: VecDeque<usize> = VecDeque::new(); for (i, &num) in nums.iter().enumerate() { // 移除所有小于当前元素值的索引 while let Some(&back) = deque.back() { if nums[back] < num { deque.pop_back(); } else { break; } } deque.push_back(i); // 移除不在滑动窗口内的元素的索引 if let Some(&front) = deque.front() { if front <= i - k { deque.pop_front(); } } // 当窗口大小为k时，记录当前窗口的最大值 if i >= k - 1 { if let Some(&front) = deque.front() { result.push(nums[front]); } } } result } fn main() { let nums = vec![1, 3, -1, -3, 5, 3, 6, 7]; let k = 3; let max_values = max_sliding_window(nums, k); println!("{:?}", max_values); }
这段 Rust 代码定义了一个max_sliding_window函数，它接受一个整数向量nums和一个 usize 类型的k作为参数，并返回一个向量，其中包含每个滑动窗口的最大值。在main函数中，我们创建了一个示例向量和窗口大小，调用了max_sliding_window函数，并打印了结果。
总结
上面的解法采用了一个有效的数据结构——双端队列（deque），来解决滑动窗口最大值的问题。这种方法的核心思想是保持双端队列的递减性质，使得队列的前端始终是当前窗口的最大值。以下是解法的步骤总结：
-
遍历输入数组
nums，对于每个元素进行以下操作：- 如果双端队列不为空且当前元素索引与队列前端元素索引之差大于或等于窗口大小
k，则将队列前端元素移除。这确保了队列中所有元素都在当前滑动窗口内。 - 从队列后端开始，移除所有小于当前元素值的元素索引。这是为了维护队列的递减性质，因为这些元素不可能是当前或未来窗口的最大值。
- 将当前元素的索引添加到队列的后端。
- 当遍历到第
k个元素及以后时（即形成了第一个完整的滑动窗口），将队列前端的元素值（当前窗口的最大值）添加到结果数组中。
- 如果双端队列不为空且当前元素索引与队列前端元素索引之差大于或等于窗口大小
-
当所有元素都被处理后，返回结果数组，该数组包含了每个滑动窗口的最大值。
这种方法的时间复杂度是O(n)，其中n是数组nums的长度，因为每个元素最多被加入和移除队列一次。空间复杂度是O(k)，其中k是滑动窗口的大小，这是因为双端队列在最坏情况下存储的元素数量不会超过窗口的大小。