算法:滑动窗口最大值
13122256420
657
2024-02-26

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

输入:nums = [1,3,-1,-3,5,3,6,7], k = 3
输出:[3,3,5,5,6,7]
解释:
滑动窗口的位置                最大值
---------------               -----
[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       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7
js版本(纯纯 3个一组,取每组 最大值)
function max_sliding_window() {
    let nums = [1, 3, 1, 3, 5, 3, 6, 7]
    let k = 3

    let res = []
    let deque = []

    for (let i = 0; i < nums.length; i++) {
        // 把 最大值 添加到 deque 队列里面去
        deque.push(nums[i])
        var d = JSON.parse(JSON.stringify(deque))
        if (i > k - 1) {
            deque.shift()
            console.log(deque)
            res.push(d.sort().reverse()[0])
        } else if (i === k - 1) {
            console.log(deque)
            // 将 0 到 k 个的元素最大值添加到 res
            res.push(d.sort().reverse()[0])
        }
    }

    console.log(res)

}
go版本(妥妥取每次最大值)
func max_sliding_window() {
	var nums = []int{1, 3, 1, 3, 5, 3, 6, 7}
	var k = 3

	var res []int
	var deque []int

	for i := 0; i < len(nums); i++ {

		// 保持 deque 队列 里面的队首 值是最大的
		for true {
			if len(deque) != 0 && deque[len(deque)-1] < nums[i] {
				deque = deque[:len(deque)-1]
			} else {
				break
			}
		}
		// 把最大值添加到 队首
		deque = append(deque, nums[i])
		fmt.Println(deque)

		if i > k-1 {
			//注意  i -k
			// 删除掉队列首 等于 数组[i-k] 最前元素
			if len(deque) != 0 && deque[0] == nums[i-k] {
				deque = deque[1:]
			}
			res = append(res, deque[0])
		} else if i == k-1 {
			res = append(res, deque[0])
		}
	}

	fmt.Println(res)

}
rust版本
fn max_sliding_window() {
    println!("移动滑块");

    let nums = vec![1, 3, 1, 3, 5, 3, 6, 7];
    let k = 3;

    let mut res: Vec<i32> = Vec::new();
    let mut deque: VecDeque<i32> = VecDeque::new();

    for i in 0..nums.len() {
        println!("{}=== {:?}", i, res);
        // 当前队列 不为空 且 当前队列最后一个元素 小于 当前循环元素
        // 小于 清空队列最后一个元素  (只保留最大值)
        // 大于 就跳出 while 循环
        while !deque.is_empty() && *deque.back().unwrap() < nums[i] {
            deque.pop_back();
        }
        deque.push_back(nums[i]);
        if i > k - 1 {
            // 队列不为空  切 队首元素 和 当前循环的首位元素 相等  就移除 队列首位元素
            if !deque.is_empty() && *deque.front().unwrap() == nums[i - k] {
                deque.pop_front();
            }

            res.push(*deque.front().unwrap());
        } else if i == k - 1 {// 相当于 刚好是 k 个数组的窗口啦  (k-1 是索引从0开始的原因) 取 deque前面的值(deque队列只保留的最大值)
            res.push(*deque.front().unwrap());
        }
    }

    println!("{:?}", res);
}