題目:
給定一個數組 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
提示:
你可以假設 k 總是有效的,在輸入數組不為空的情況下,1 ≤ k ≤ 輸入數組的大小。
進階:
你能在線性時間複雜度內解決此題嗎?
解題思路:研究了下各路大神的代碼,採用雙端隊列法,可以達到線性時間複雜度。這裡用鏈表實現隊列。也可以使用切片來處理。
<code>type Node struct { index int value int next *Node } //主調用函數 func maxSlidingWindow(nums []int, k int) []int { var head *Node ret := make([]int, 0) //存儲結果集 for i := 0; i < len(nums); i++ { if head == nil { head = new(Node) head.index = i head.value = nums[i] } else if i-head.index >= k { //head 滑出窗口 head = head.next i-- continue } else if head.value <= nums[i] { //遇到比頭結點更大的數,新建隊列 head = &Node{index: i, value: nums[i]} } else { //降序排列 p := head for p.next != nil { if p.next.value > nums[i] { p = p.next } else { break } } p.next = &Node{index: i, value: nums[i]} } if i >= k-1 { ret = append(ret, head.value) } } return ret }/<code>
執行用時:24ms
使用切片來處理,隊列記錄index:
<code>func maxSlidingWindow(nums []int, k int) []int { if k <= 1 { return nums } ret := make([]int, 0) queue := make([]int, 0, k) //存儲index for i := 0; i < len(nums); i++ { if len(queue) == 0 { queue = append(queue, i) continue } if i-queue[0] >= k { //滑出窗口 queue = queue[1:] } if nums[queue[len(queue)-1]] > nums[i] { queue = append(queue, i) } else { for j := 0; j < len(queue); j++ { if nums[queue[j]] <= nums[i] { queue[j] = i queue = queue[:j+1] break } } } if i >= k-1 { ret = append(ret, nums[queue[0]]) } } return ret }/<code>
執行用時:12 ms, 在所有 Go 提交中擊敗了100.00%的用戶
內存消耗:6.4 MB, 在所有 Go 提交中擊敗了100.00%的用戶