[Swift]LeetCode239. 滑动窗口最大值 | Sliding Window Maximum

概述Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window m

Given an array nums,there is a slIDing window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the slIDing window moves right by one position. Return the max slIDing window.

Example:

input: nums =,and k = 3Output: Window position                Max---------------               -----[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[1,3,-1,-3,5,6,7][3,7] Explanation:

Note: 
You may assume k is always valID,1 ≤ k ≤ input array‘s size for non-empty array.

Follow up:
Could you solve it in linear time?

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

返回滑动窗口最大值。

示例:

输入: nums =,和 k = 3输出:   滑动窗口的位置                最大值---------------               -----[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[1,7] 解释:

注意：

你可以假设 k 总是有效的，1 ≤ k ≤ 输入数组的大小，且输入数组不为空。

进阶：

你能在线性时间复杂度内解决此题吗？

168ms

 1 class Solution { 2     func maxSlIDingWindow(_ nums: [Int],_ k: Int) -> [Int] { 3         guard k > 0 && nums.count >= k else { 4             return [] 5         } 6          7         if k == 1 { 8             return nums 9         }10         var res = [Int]()11         var max_tuple = (nums[0],0)12         13         for i in 0..<k {14             if nums[i] > max_tuple.0 {15                 max_tuple = (nums[i],i)16             }17         }18         res.append(max_tuple.0)19         for i in k..<nums.count {20             21             if nums[i] > max_tuple.0 {22                 max_tuple = (nums[i],i)23             } else if max_tuple.1 == (i-k){24                 var pos = max_tuple.125                 max_tuple = (nums[i],i)26                 for j in (pos + 1)...(i-1) {27                     if nums[j] > max_tuple.0 {28                         max_tuple = (nums[j],j)29                     }30                 }31             }32             res.append(max_tuple.0)33         }34         35         return res36     }37 }

184ms

 1 class Solution { 2     func maxSlIDingWindow(_ nums: [Int],_ k: Int) -> [Int] { 3         guard nums.count > 0 && k > 0 else { return [] } 4         var i = 0 5         var maxWindow = [Int]() 6         while k + i <= nums.count { 7             let slice = nums[i..<i+k] 8             if maxWindow.count == 0 { 9                 maxWindow.append(slice.max()!)10             } else {11                 let lastMax = maxWindow.last!12                 if lastMax == nums[i - 1] {13                     maxWindow.append(slice.max()!)14                 } else {15                     maxWindow.append(max(lastMax,slice.last!))16                 }17             }18             19             i += 120         }21         return maxWindow22     }23 }

188ms

 1 class Solution { 2     func maxSlIDingWindow(_ nums: [Int],_ k: Int) -> [Int] { 3         if k > nums.count { 4             return [] 5         } 6          7         var result = [Int]() 8          9         var bIDirectionalQueue = [Int]()10         11         for i in 0..<nums.count {12             13             while(!bIDirectionalQueue.isEmpty && bIDirectionalQueue[0]+k <= i) {14                 bIDirectionalQueue.remove(at: 0)15             }16             17             while(!bIDirectionalQueue.isEmpty && nums[bIDirectionalQueue[bIDirectionalQueue.count - 1]] < nums[i]) {18                 bIDirectionalQueue.removeLast()19             }20             21             bIDirectionalQueue.append(i)22             23             if i >= k-1 {24                 result.append(nums[bIDirectionalQueue[0]])25             }26         }27         28         return result29     }30 }

204ms

 1 class Solution { 2     func maxSlIDingWindow(_ nums: [Int],_ k: Int) -> [Int] { 3 if nums.isEmpty || k <= 0 { 4         return [] 5     } 6     var window: [Int] = [],res: [Int] = [] 7     for i in 0..<nums.count { 8         let x = nums[i] 9         if i >= k && window[0] <= i - k {10             window.removeFirst()11         }12         while !window.isEmpty && nums[window.last!] <= x {13             window.popLast()14         }15         window.append(i)16         if i >= k - 1 {17             res.append(nums[window.first!])18         }19     }20     return res21     }22 }

208ms

 1 class Solution { 2     func maxSlIDingWindow(_ nums: [Int],_ k: Int) -> [Int] { 3         guard nums.count > 0 else { return [] } 4          5         var output: [Int] = [] 6         var deQueue: [Int] = [] 7         let n = nums.count 8         for index in 0..<k { 9             while deQueue.count > 0 && nums[index] >= nums[deQueue.last!] {10                 deQueue.removeLast()11             }12             deQueue.append(index)13         }14         for index in k..<n {15             output.append(nums[deQueue.first!])16             17             while deQueue.count > 0 && deQueue.first! <= index - k  {18                 deQueue.removeFirst()19             }20             21              while deQueue.count > 0 && nums[index] >= nums[deQueue.last!] {22                 deQueue.removeLast()23             }24             deQueue.append(index)            25         }26         27         output.append(nums[deQueue.first!])28         return output29     }30 }

212ms

 1 class Solution { 2     func maxSlIDingWindow(_ nums: [Int],_ k: Int) -> [Int] { 3         var answer = [Int]() 4         var q = [Int]() 5  6         for i in 0..<nums.count { 7             while !q.isEmpty && q.first! < i - k + 1 { 8                 q.removeFirst() 9             }10 11             while !q.isEmpty && nums[q.last!] < nums[i] {12                 q.removeLast()13             }14 15             q.append(i)16 17             if i >= k - 1 {18                 answer.append(nums[q.first!])19             }20         }21 22         return answer23     }24 }

224ms

 1 class MonQueue { 2     private var queue = [Int]() 3      4     func push(_ el: Int) { 5         while !queue.isEmpty && queue.last! < el { 6             queue.removeLast() 7         } 8          9         queue.append(el)10     }11     12     func pop(_ el: Int) {13         if !queue.isEmpty && queue.first! == el {14             queue.removeFirst()15         }16     }17     18     func front() -> Int? {19         return queue.first20     }21 }22 class Solution {23     func maxSlIDingWindow(_ nums: [Int],_ k: Int) -> [Int] {24         var res = [Int]()25         26         guard nums.count > 0 else {27             return res28         }29         30         var monQueue = MonQueue()31         32         for i in 0..<k {33             monQueue.push(nums[i])34         }35         36         res.append(monQueue.front()!)37         38         for i in k..<nums.count {39             let elToRemove = nums[i-k]40             let elToAdd = nums[i]41             monQueue.push(elToAdd)42             monQueue.pop(elToRemove)43             res.append(monQueue.front()!)44         }45         46         return res47     }48 }

256ms

 1 class Solution { 2     func maxSlIDingWindow(_ nums: [Int],_ k: Int) -> [Int] { 3  4         var res = [Int]() 5         var q = [Int]() 6         for (i,num) in nums.enumerated() { 7             if !q.isEmpty,q.first! == i-k { q.removeFirst() } 8             while !q.isEmpty,nums[q.last!] < num { q.removeLast() } 9             q.append(i)10             if i >= k-1 { res.append(nums[q.first!])}11         }12         return res13     }14 }

总结

以上是内存溢出为你收集整理的[Swift]LeetCode239. 滑动窗口最大值 | Sliding Window Maximum全部内容，希望文章能够帮你解决[Swift]LeetCode239. 滑动窗口最大值 | Sliding Window Maximum所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。