239. Sliding Window Maximum解題報告

Description:

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.
Note:
You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.

Follow up:
Could you solve it in linear time?

Example:

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

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

Therefore, return the max sliding window as [3,3,5,5,6,7].

Link:

https://leetcode.com/problems/sliding-window-maximum/description/

解題方法:

如果我們能有一個維持descending的結(jié)構(gòu)儲存window里面的數(shù)字痕支,那么這個問題就很容易解決沿侈。
max heap可以滿足我們的需求亿驾,但是每次刪除數(shù)字會額外耗費時間漩绵。
雙向隊列可以滿足線性的要求,我們可以手動維護隊列的順序逗扒,當(dāng)隊尾的元素小于新來的元素都哭,就pop_back,隊頭的元素維持當(dāng)前窗口最大延欠,當(dāng)隊頭的元素不在窗口范圍內(nèi),就pop_front沈跨。

為什么當(dāng)隊尾的元素小于最先來的元素可以直接pop而不是存下來接著排序呢由捎?
因為我們已經(jīng)有了比他們還要大的,新的元素到來饿凛,當(dāng)這個新的元素沒有過期時(在窗口范圍內(nèi))狞玛,那些需要pop的元素永遠不可能成為最大的元素邻奠。當(dāng)這個新的元素過期時,那些需要pop的元素都肯定過期为居。所以我們可以直接pop掉不用保留下來碌宴。

Tips:

Time Complexity:

O(N)

完整代碼:

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> result;
    deque<int> Q;
    for(int i = 0; i < nums.size(); i++) {
        while(!Q.empty() && i - k >= Q.front())
            Q.pop_front();
        while(!Q.empty() && nums[i] > nums[Q.back()])
            Q.pop_back();
        Q.push_back(i);
        if(i >= k - 1)
            result.push_back(nums[Q.front()]);
    }
    return result;
}
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市蒙畴,隨后出現(xiàn)的幾起案子贰镣,更是在濱河造成了極大的恐慌,老刑警劉巖膳凝,帶你破解...
    沈念sama閱讀 222,865評論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件碑隆,死亡現(xiàn)場離奇詭異,居然都是意外死亡蹬音,警方通過查閱死者的電腦和手機上煤,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,296評論 3 399
  • 文/潘曉璐 我一進店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來著淆,“玉大人劫狠,你說我怎么就攤上這事∮啦浚” “怎么了独泞?”我有些...
    開封第一講書人閱讀 169,631評論 0 364
  • 文/不壞的土叔 我叫張陵,是天一觀的道長苔埋。 經(jīng)常有香客問我懦砂,道長,這世上最難降的妖魔是什么组橄? 我笑而不...
    開封第一講書人閱讀 60,199評論 1 300
  • 正文 為了忘掉前任荞膘,我火速辦了婚禮,結(jié)果婚禮上玉工,老公的妹妹穿的比我還像新娘羽资。我一直安慰自己,他們只是感情好瓮栗,可當(dāng)我...
    茶點故事閱讀 69,196評論 6 398
  • 文/花漫 我一把揭開白布削罩。 她就那樣靜靜地躺著,像睡著了一般费奸。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上进陡,一...
    開封第一講書人閱讀 52,793評論 1 314
  • 那天愿阐,我揣著相機與錄音,去河邊找鬼趾疚。 笑死缨历,一個胖子當(dāng)著我的面吹牛以蕴,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播辛孵,決...
    沈念sama閱讀 41,221評論 3 423
  • 文/蒼蘭香墨 我猛地睜開眼丛肮,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了魄缚?” 一聲冷哼從身側(cè)響起宝与,我...
    開封第一講書人閱讀 40,174評論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎冶匹,沒想到半個月后习劫,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,699評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡嚼隘,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,770評論 3 343
  • 正文 我和宋清朗相戀三年诽里,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片飞蛹。...
    茶點故事閱讀 40,918評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡谤狡,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出卧檐,到底是詐尸還是另有隱情豌汇,我是刑警寧澤,帶...
    沈念sama閱讀 36,573評論 5 351
  • 正文 年R本政府宣布泄隔,位于F島的核電站拒贱,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏佛嬉。R本人自食惡果不足惜逻澳,卻給世界環(huán)境...
    茶點故事閱讀 42,255評論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望暖呕。 院中可真熱鬧斜做,春花似錦、人聲如沸湾揽。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,749評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽库物。三九已至霸旗,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間戚揭,已是汗流浹背诱告。 一陣腳步聲響...
    開封第一講書人閱讀 33,862評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留民晒,地道東北人精居。 一個月前我還...
    沈念sama閱讀 49,364評論 3 379
  • 正文 我出身青樓锄禽,卻偏偏與公主長得像,于是被迫代替她去往敵國和親靴姿。 傳聞我的和親對象是個殘疾皇子沃但,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,926評論 2 361

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

  • 背景 一年多以前我在知乎上答了有關(guān)LeetCode的問題, 分享了一些自己做題目的經(jīng)驗。 張土汪:刷leetcod...
    土汪閱讀 12,749評論 0 33
  • 思念是冬天的籽,春天的芽辈毯,是陰天的冷冷微涼的風(fēng)坝疼,是午后突然的茫然和空缺,是抓不住的空氣谆沃,是郁郁蔥蔥的綠色里紅色的喜...
    蘆葦初音閱讀 184評論 0 1
  • 下午足足兩個多小時的組會钝凶,倍感煎熬,倒不是因為以后要降工資唁影,以后要自己插槍頭耕陷,都是糟心的課題,沒有進展据沈,重復(fù)不出來...
    饃饃_99閱讀 165評論 0 0
  • 練習(xí)「每日千字文」就是每天寫超過一千字的文章哟沫,命名為「每日千字文計劃」。這是一件長期的訓(xùn)練锌介,在寫的過程中嗜诀,會發(fā)現(xiàn)很...
    荷小音閱讀 1,033評論 2 6
  • 我行經(jīng)此路 愿泛金鸚鵡 意中如有得 把臂歡不足 我心常所慕 的的暗更徐 心苦為分明 交態(tài)知浮俗 給謠紫芝曲 田廷備...
    你的苒閱讀 146評論 0 0