題目描述:給定一個數(shù)組 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
提示:你可以假設(shè) k 總是有效的彬伦,在輸入數(shù)組不為空的情況下嫂用,1 ≤ k ≤ 輸入數(shù)組的大小。
題解一:循環(huán)暴力破解
解題思路:從數(shù)組第i(i=0)個數(shù)據(jù)開始,將其與其后第i+1..<i+k依次進行比較取最大值,直至遍歷到第count-k+1泽篮,得到最后一個窗口中的最大值為止镣典。
解題開發(fā)語言: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
}
}
缺點:存在重復(fù)比較,以示例中的數(shù)據(jù)[1,3,-1,-3,5,3,6,7]竹伸,3為例,1,3,-1中最大數(shù)據(jù)為3,窗口滑動晦嵌,比較3,-1,-3中最大值為3,其中3與-1被重復(fù)比較了兩次拷姿。
復(fù)雜度分析:
時間復(fù)雜度:O(n), 其中n為數(shù)組長度惭载,外層for循環(huán)執(zhí)行n-k+1次,內(nèi)層for循環(huán)每次執(zhí)行k次响巢,所以總共是k(n-k+1), 忽略乘數(shù)因子等描滔,所以是O(n)
空間復(fù)雜度:O(1), 運算過程中未額外開辟內(nèi)存
題解二:雙端隊列
解題思路:以示例中數(shù)據(jù)為例,第一組窗口數(shù)據(jù)是踪古,1,3,-1, 由于后面的3比前面的1打含长,所以當(dāng)比較-1時,前面的1對比較結(jié)果是沒有意義的伏穆,因為3比它大拘泞,1不可能是這組數(shù)據(jù)里的最大值了,所有按照這個思路枕扫,可以創(chuàng)建一個隊列陪腌,將數(shù)組中的數(shù)據(jù)依次入隊,但是由于我們求最大值烟瞧,所以當(dāng)一個數(shù)據(jù)入隊前诗鸭,將其與隊尾的數(shù)據(jù)進行比較,如果隊尾數(shù)據(jù)比當(dāng)前數(shù)據(jù)小参滴,即隊尾數(shù)據(jù)在此次窗口數(shù)據(jù)中不可能是最大值强岸,所以其可以直接出隊,由于其要從隊尾出隊砾赔,所以創(chuàng)建的這個隊列有點特殊蝌箍,需要是一個雙端隊列青灼,然后將當(dāng)前數(shù)據(jù)入隊,隊列中最多需要保持最多k個數(shù)據(jù)十绑,當(dāng)隊列中已經(jīng)存在k個數(shù)據(jù)時聚至,新數(shù)據(jù)入隊前,將隊首數(shù)據(jù)直接出棧本橙,因為其不在本次窗口的比較范圍內(nèi)扳躬,當(dāng)窗口形成后,隊首數(shù)據(jù)即為窗口最大數(shù)據(jù)甚亭。
// 雙向隊列
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
}
// 數(shù)組前方有空余空間, 需要做數(shù)據(jù)搬移
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]
// 移除隊列中比當(dāng)前值小的數(shù)據(jù)贷币,因為最大值肯定不是這些數(shù)據(jù)
while (!doubleQueue.isEmpty && val > nums[doubleQueue.trail!]) {
doubleQueue.dequeueBack()
}
if doubleQueue.prev != nil && doubleQueue.prev! < i - k + 1 {
doubleQueue.dequeue()
}
// 將當(dāng)前值入隊
doubleQueue.enqueue(val: i)
// 如果是第三個及之后的數(shù)據(jù),滑動窗口每移動一次亏狰,需保存一次最大值
if i + 1 >= k {
result[i - k + 1] = nums[doubleQueue.prev!]
}
}
return result
}
}
復(fù)雜度分析
時間復(fù)雜度:O(n), n為數(shù)組長度役纹,遍歷數(shù)組時間為O(n), 整個遍歷過程中每個元素最多入隊和出隊1次,所以隊列操作為O(2n), 所以總的時間復(fù)雜度為O(n) + O(2n) = O(3n), 忽略乘數(shù)因子即為O(n)
空間復(fù)雜度:O(k), 雙端隊列中最多存在k個數(shù)據(jù)(窗口大邢就佟)