[Swift]LeetCode239.滑动窗口最大值|SlidingWindowMaximum

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10205182.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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

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

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 = [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 ≤ 输入数组的大小，且输入数组不为空。

进阶：

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

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.1
25                 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 res
36     }
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 += 1
20         }
21         return maxWindow
22     }
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 result
29     }
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 res
21     }
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 output
29     }
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 answer
23     }
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.first
20     }
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 res
28         }
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 res
47     }
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 res
13     }
14 }