筆試面試題目：滑動視窗(二)

算法：

這算是滑動視窗的另外一個典型題目，在資料量比較少的時候，可以直接采用暴力法解決；不過資料量比較大的時候，我們就需要想辦法解決視窗裡面最大值的思路，這裡我們采用雙端隊列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
}
           

執行結果：