算法：滑动窗口(二)

灰子学技术

发布于 2020-10-10 16:55:04

3540

发布于 2020-10-10 16:55:04

文章被收录于专栏：灰子学技术灰子学技术

算法：

这算是滑动窗口的另外一个典型题目，在数据量比较少的时候，可以直接采用暴力法解决；不过数据量比较大的时候，我们就需要想办法解决窗口里面最大值的思路，这里我们采用双端队列queue来实现，借助 queue来保存前面计算过的最大值信息。

题目:

https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/

解法1:

暴力解法：按照窗口大小，从头到尾依次遍历，将每个窗口中的最大值存储到输出的结果中。

func maxSlidingWindow(nums []int, k int) []int {
    if len(nums) < k || len(nums)==0{
        return nil
    }
    
    res := []int{}
    // 滑动窗口的左指针的遍历范围
    for l := 0; l<= len(nums)-k;l++ {
        max := nums[l]
        // 滑动窗口的窗口大小遍历比较
        for r := l+1; r<l+k; r++ {
            if max < nums[r] {
                max = nums[r]
            }
        }
        res =append(res,max)
    }
    return res
}

执行结果：

解法2:

利用双端队列来存储计算过的最大数据，queue来存储遍历过的最大数据，一旦当前元素比queue中的大，就需要将比当前元素小的数据移除；并且保证queue[0]作为每个窗口计算的最大值。

func maxSlidingWindow(nums []int, k int) []int {
    if len(nums)==0{
        return nil
    }
    queue := []int{}
    res := []int{}
    // 用双端队列queue来计算最大值
    for l := 0; l< len(nums);l++ {
        for l>0 && (len(queue)>0) && nums[l]>queue[len(queue)-1] {            // 删除queue中比当前元素小的所有的数，所以是个循环擦欧哦
            // 删除queue中比当前元素小的所有的数据，这里是个循环
            queue = queue[:len(queue)-1]
        }
        // 将大的数字加入双端队列
        queue =append(queue,nums[l])
        // left右移一个窗口大小之后，queue里面的元素需要删除0位置的数字
        if l>=k && nums[l-k] == queue[0] {
            queue = queue[1:]
        }
        // 每个窗口的最大值 放到res中
        if l>= k-1 {
            res = append(res,queue[0])
        }
    }
    return res
}

执行结果：