题目描述：给定一个数组 nums 和滑动窗口的大小 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 ≤ 输入数组的大小。
题解一：循环暴力破解
解题思路：从数组第i（i=0）个数据开始，将其与其后第i+1..<i+k依次进行比较取最大值，直至遍历到第count-k+1，得到最后一个窗口中的最大值为止。
解题开发语言：Swift
class Solution {
func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
if nums.count <= 1 || k == 1 {
return nums
}
var result = [Int]()
for i in 0..<nums.count-k+1 {
var maxNum = Int.min
for j in i..<i+k {
maxNum = max(maxNum, nums[j])
}
result.append(maxNum)
}
return result
}
}
缺点：存在重复比较，以示例中的数据[1,3,-1,-3,5,3,6,7]，3为例，1,3,-1中最大数据为3，窗口滑动，比较3,-1,-3中最大值为3，其中3与-1被重复比较了两次。
复杂度分析：
时间复杂度：O(n), 其中n为数组长度，外层for循环执行n-k+1次，内层for循环每次执行k次，所以总共是k(n-k+1), 忽略乘数因子等，所以是O(n)
空间复杂度：O(1), 运算过程中未额外开辟内存
题解二：双端队列
解题思路：以示例中数据为例，第一组窗口数据是，1,3,-1, 由于后面的3比前面的1打，所以当比较-1时，前面的1对比较结果是没有意义的，因为3比它大，1不可能是这组数据里的最大值了，所有按照这个思路，可以创建一个队列，将数组中的数据依次入队，但是由于我们求最大值，所以当一个数据入队前，将其与队尾的数据进行比较，如果队尾数据比当前数据小，即队尾数据在此次窗口数据中不可能是最大值，所以其可以直接出队，由于其要从队尾出队，所以创建的这个队列有点特殊，需要是一个双端队列，然后将当前数据入队，队列中最多需要保持最多k个数据，当队列中已经存在k个数据时，新数据入队前，将队首数据直接出栈，因为其不在本次窗口的比较范围内，当窗口形成后，队首数据即为窗口最大数据。
// 双向队列
struct DoubleQueue {
private var data = [Int]()
private var n = 0, pre = 0, tra = 0
public var trail: Int? {
if isEmpty {
return nil
}
return data[tra - 1]
}
public var prev: Int? {
if isEmpty {
return nil
}
return data[pre]
}
public var total: Int {
return tra - pre
}
public var isEmpty: Bool {
return tra - pre == 0
}
init(num: Int) {
n = num
pre = 0
tra = 0
data = [Int](repeating: Int.min, count: num)
}
@discardableResult
public mutating func enqueue(val: Int) -> Bool {
if total == n {
return false
}
// 数组前方有空余空间, 需要做数据搬移
if tra == n && pre > 0 {
for i in pre..<tra {
data[i-pre] = data[i]
}
tra -= pre
pre = 0
}
data[tra] = val
tra += 1
return true
}
@discardableResult
public mutating func enqueueFront(val: Int) -> Bool {
if total == n {
return false
}
pre = pre > 0 ? pre - 1 : 0
data.insert(val, at: pre)
return true
}
@discardableResult
public mutating func dequeue() -> Int? {
if total == 0 {
return nil
}
let val = data[pre]
pre += 1
return val
}
@discardableResult
public mutating func dequeueBack() -> Int? {
if total == 0 {
return nil
}
let val = data[tra - 1]
tra -= 1
return val
}
}
class Solution {
func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
if nums.count <= 1 || k <= 1 {
return nums
}
var result = [Int](repeating: Int.min, count: nums.count - k + 1)
var doubleQueue = DoubleQueue(num: k)
for i in 0..<nums.count {
let val = nums[i]
// 移除队列中比当前值小的数据，因为最大值肯定不是这些数据
while (!doubleQueue.isEmpty && val > nums[doubleQueue.trail!]) {
doubleQueue.dequeueBack()
}
if doubleQueue.prev != nil && doubleQueue.prev! < i - k + 1 {
doubleQueue.dequeue()
}
// 将当前值入队
doubleQueue.enqueue(val: i)
// 如果是第三个及之后的数据，滑动窗口每移动一次，需保存一次最大值
if i + 1 >= k {
result[i - k + 1] = nums[doubleQueue.prev!]
}
}
return result
}
}
复杂度分析
时间复杂度：O(n), n为数组长度，遍历数组时间为O(n), 整个遍历过程中每个元素最多入队和出队1次，所以队列操作为O(2n), 所以总的时间复杂度为O(n) + O(2n) = O(3n), 忽略乘数因子即为O(n)
空间复杂度：O(k), 双端队列中最多存在k个数据（窗口大小）
网友评论