LeetCode習(xí)題:滑動窗口的最大值

題目描述:給定一個數(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ù)(窗口大邢就佟)
題目來源:LeetCode
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末促脉,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子策州,更是在濱河造成了極大的恐慌瘸味,老刑警劉巖,帶你破解...
    沈念sama閱讀 218,858評論 6 508
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件够挂,死亡現(xiàn)場離奇詭異旁仿,居然都是意外死亡,警方通過查閱死者的電腦和手機孽糖,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,372評論 3 395
  • 文/潘曉璐 我一進店門枯冈,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人办悟,你說我怎么就攤上這事尘奏。” “怎么了病蛉?”我有些...
    開封第一講書人閱讀 165,282評論 0 356
  • 文/不壞的土叔 我叫張陵炫加,是天一觀的道長。 經(jīng)常有香客問我铡恕,道長琢感,這世上最難降的妖魔是什么丢间? 我笑而不...
    開封第一講書人閱讀 58,842評論 1 295
  • 正文 為了忘掉前任探熔,我火速辦了婚禮,結(jié)果婚禮上烘挫,老公的妹妹穿的比我還像新娘诀艰。我一直安慰自己柬甥,他們只是感情好,可當(dāng)我...
    茶點故事閱讀 67,857評論 6 392
  • 文/花漫 我一把揭開白布其垄。 她就那樣靜靜地躺著苛蒲,像睡著了一般。 火紅的嫁衣襯著肌膚如雪绿满。 梳的紋絲不亂的頭發(fā)上臂外,一...
    開封第一講書人閱讀 51,679評論 1 305
  • 那天,我揣著相機與錄音喇颁,去河邊找鬼漏健。 笑死,一個胖子當(dāng)著我的面吹牛橘霎,可吹牛的內(nèi)容都是我干的蔫浆。 我是一名探鬼主播,決...
    沈念sama閱讀 40,406評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼姐叁,長吁一口氣:“原來是場噩夢啊……” “哼瓦盛!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起外潜,我...
    開封第一講書人閱讀 39,311評論 0 276
  • 序言:老撾萬榮一對情侶失蹤原环,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后橡卤,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體扮念,經(jīng)...
    沈念sama閱讀 45,767評論 1 315
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,945評論 3 336
  • 正文 我和宋清朗相戀三年碧库,在試婚紗的時候發(fā)現(xiàn)自己被綠了柜与。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 40,090評論 1 350
  • 序言:一個原本活蹦亂跳的男人離奇死亡嵌灰,死狀恐怖弄匕,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情沽瞭,我是刑警寧澤迁匠,帶...
    沈念sama閱讀 35,785評論 5 346
  • 正文 年R本政府宣布,位于F島的核電站驹溃,受9級特大地震影響城丧,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜豌鹤,卻給世界環(huán)境...
    茶點故事閱讀 41,420評論 3 331
  • 文/蒙蒙 一亡哄、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧布疙,春花似錦蚊惯、人聲如沸愿卸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,988評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽趴荸。三九已至,卻和暖如春宦焦,著一層夾襖步出監(jiān)牢的瞬間发钝,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,101評論 1 271
  • 我被黑心中介騙來泰國打工波闹, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留笼平,地道東北人。 一個月前我還...
    沈念sama閱讀 48,298評論 3 372
  • 正文 我出身青樓舔痪,卻偏偏與公主長得像寓调,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子锄码,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,033評論 2 355

推薦閱讀更多精彩內(nèi)容