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

发布时间：2020-12-14 05:07:40 所属栏目：百科来源：网络整理

导读：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

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 = 3
Output: 
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.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 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!