LeetCode 之 JavaScript 解答第69題 —— X 的平方根(Squrt(x))


Time:2019/4/16
Title: Sliding Window Maximum
Difficulty: Difficulty
Author: 小鹿


題目:Sliding Window Maximum

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.

給定一個(gè)數(shù)組 nums,有一個(gè)大小為 k 的滑動(dòng)窗口從數(shù)組的最左側(cè)移動(dòng)到數(shù)組的最右側(cè)荆残。你只可以看到在滑動(dòng)窗口 k 內(nèi)的數(shù)字。滑動(dòng)窗口每次只向右移動(dòng)一位。

返回滑動(dòng)窗口最大值。

Example:

Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7] 
Explanation: 

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

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?

Solve:

▉ 問(wèn)題分析

暴力破解法

1)看到這個(gè)題目最容易想到的就是暴力破解法锣吼,借助一個(gè) for 循環(huán),兩個(gè)變量蓝厌,整體移動(dòng)窗口玄叠,然后每移動(dòng)一次就在大小為 k 的窗口求出最大值。

2)但是這樣的解決效率非常低拓提,如果數(shù)據(jù)非常大時(shí)读恃,共有 n1 個(gè)數(shù)據(jù),窗口大小為 n2(n1 遠(yuǎn)遠(yuǎn)大于 n2),時(shí)間復(fù)雜度為 n2(n1 - n2) 狐粱。也就是 n1 * n2舀寓,最壞時(shí)間復(fù)雜度為 n^2。

優(yōu)先級(jí)隊(duì)列

1)每次移動(dòng)窗口求最大值肌蜻,以及在動(dòng)態(tài)數(shù)據(jù)中求最大值互墓,我們想到的就是優(yōu)先級(jí)隊(duì)列,而優(yōu)先級(jí)隊(duì)列的實(shí)現(xiàn)是堆這種數(shù)據(jù)結(jié)構(gòu)蒋搜,這道題用堆解決效率更高篡撵。如果對(duì)堆不熟悉,趕緊給自己補(bǔ)補(bǔ)功課吧豆挽!底部有我寫(xiě)的文章鏈接育谬。

2)通過(guò)堆的優(yōu)化,向堆中插入數(shù)據(jù)時(shí)間復(fù)雜度為 logn 帮哈,所以時(shí)間復(fù)雜度為 nlogn膛檀。

▉ 算法思路

暴力破解法:

1)用兩個(gè)指針,分別指向窗口的起始位置和終止位置娘侍,然后遍歷窗口中的數(shù)據(jù)咖刃,求出最大值;向前移動(dòng)兩個(gè)指針憾筏,然后操作嚎杨,直到遍歷數(shù)據(jù)完成位置。

優(yōu)先級(jí)隊(duì)列:

1)需要維護(hù)大小為 k 的大頂堆氧腰,堆頂就是當(dāng)前窗口最大的數(shù)據(jù)枫浙,當(dāng)移動(dòng)窗口時(shí),如果插入的數(shù)據(jù)大于堆頂?shù)臄?shù)據(jù)古拴,將其加入到結(jié)果集中箩帚。同時(shí)要?jiǎng)h除數(shù)據(jù),如果刪除的數(shù)據(jù)為最大數(shù)據(jù)且插入的數(shù)據(jù)小于刪除的數(shù)據(jù)時(shí)斤富,向大小為 k 的以 logn 的時(shí)間復(fù)雜度插入膏潮,返回堆頂元素。

▉ 暴力破解法

var maxSlidingWindow = function(nums, k) {
    if(k > nums.length || k === 0) return [];
    let res = [], maxIndex = -1;
    for(let l = 0, r = k-1;r < nums.length;l++, r++){
        if(maxIndex < l){
            // 遍歷求出最大值
            let index = l;
            for(let i = l;i <= r;i++) {
                if(nums[i] > nums[index]) index = i;
            }
            maxIndex = index;
        }
        if(nums[r] > nums[maxIndex]){
            maxIndex = r;
        }
        res.push(nums[maxIndex]);
    }
    return res;
};
▉ 優(yōu)先級(jí)隊(duì)列
let count = 0;
let heap = [];
let n = 0;
var maxSlidingWindow = function(nums, k) {
    let pos = k;
    n = k;
    let result = [];
    let len = nums.length;

    // 判斷數(shù)組和最大窗口樹(shù)是否為空
    if(nums.length === 0 || k === 0) return result;

    // 建大頂堆
    let j = 0
    for(;j < k; j++){
        insert(nums[j]);
    }
    result.push(heap[1]); 

    // 移動(dòng)窗口
    while(len - pos > 0){
        if(nums[k] > heap[1]){
            result.push(nums[k]);
            insert(nums[k]);
            nums.shift();
            pos++; 
        }else{
            if(nums.shift() === heap[1]){
                removeMax(); 
            }
            insert(nums[k-1]);
            result.push(heap[1]);
            pos++;
        }
    }
    return result;
};  



// 插入數(shù)據(jù)
const insert = (data) =>{
    //判斷堆滿
    // if(count >= n) return; // >=

    // 插入到數(shù)組尾部
    count++
    heap[count] = data;

    //自下而上堆化
    let i = count;
    while(i / 2 > 0 && heap[i] > heap[parseInt(i/2)]){
        swap(heap,i,parseInt(i/2));
        i = parseInt(i/2);
    }
}

// 兩個(gè)數(shù)組內(nèi)元素交換
swap = (arr,x,y) =>{
    let temp = arr[x];
    arr[x] = arr[y];
    arr[y] = temp;
}

// 堆的刪除
const removeMax = () =>{
    // 判斷堆空
    if(count <= 0) return ;

    // 最大數(shù)據(jù)移到最后刪除
    heap[1] = heap[count];

    // 長(zhǎng)度減一
    count--;
    // 刪除數(shù)據(jù)
    heap.pop();

    // 從上到下堆化
    heapify(heap,count,1);
}

// 從上到下堆化
const heapify = (heap,count,i) =>{
    while(true){
        // 存儲(chǔ)堆子節(jié)點(diǎn)的最大值下標(biāo)
        let maxPos = i;

        // 左子節(jié)點(diǎn)比父節(jié)點(diǎn)大
        if(i*2 < n && heap[i*2] > heap[i]) maxPos = i*2;
        // 右子節(jié)點(diǎn)比父節(jié)點(diǎn)大
        if(i*2+1 <= n && heap[i*2+1] > heap[maxPos]) maxPos = i*2+1;

        // 如果沒(méi)有發(fā)生替換满力,則說(shuō)明該堆只有一個(gè)結(jié)點(diǎn)(父節(jié)點(diǎn))或子節(jié)點(diǎn)都小于父節(jié)點(diǎn)
        if(maxPos === i) break;

        // 交換
        swap(heap,maxPos,i);
        // 繼續(xù)堆化
        i = maxPos;
    }
}
▉ 性能分析

暴力破解法

  • 時(shí)間復(fù)雜度:O(n^2).
  • 空間復(fù)雜度:O(1).

優(yōu)先級(jí)隊(duì)列

  • 時(shí)間復(fù)雜度:nlogn.
  • 空間復(fù)雜度:O(1).
▉ 擴(kuò)展

堆:

1)堆插入焕参、刪除操作

2)如何實(shí)現(xiàn)一個(gè)堆?

3)堆排序

4)堆的應(yīng)用

詳細(xì)查看寫(xiě)的另一篇關(guān)于堆的文章:數(shù)據(jù)結(jié)構(gòu)與算法之美【堆】


歡迎一起加入到 LeetCode 開(kāi)源 Github 倉(cāng)庫(kù)油额,可以向 me 提交您其他語(yǔ)言的代碼叠纷。在倉(cāng)庫(kù)上堅(jiān)持和小伙伴們一起打卡,共同完善我們的開(kāi)源小倉(cāng)庫(kù)潦嘶!
Github:https://github.com/luxiangqiang/JS-LeetCode

歡迎關(guān)注我個(gè)人公眾號(hào):「一個(gè)不甘平凡的碼農(nóng)」涩嚣,記錄了自己一路自學(xué)編程的故事。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市航厚,隨后出現(xiàn)的幾起案子顷歌,更是在濱河造成了極大的恐慌,老刑警劉巖幔睬,帶你破解...
    沈念sama閱讀 223,002評(píng)論 6 519
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件眯漩,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡麻顶,警方通過(guò)查閱死者的電腦和手機(jī)赦抖,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,357評(píng)論 3 400
  • 文/潘曉璐 我一進(jìn)店門(mén),熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)辅肾,“玉大人队萤,你說(shuō)我怎么就攤上這事〗玫觯” “怎么了要尔?”我有些...
    開(kāi)封第一講書(shū)人閱讀 169,787評(píng)論 0 365
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)份汗。 經(jīng)常有香客問(wèn)我盈电,道長(zhǎng)蝴簇,這世上最難降的妖魔是什么杯活? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 60,237評(píng)論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮熬词,結(jié)果婚禮上旁钧,老公的妹妹穿的比我還像新娘。我一直安慰自己互拾,他們只是感情好歪今,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,237評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布。 她就那樣靜靜地躺著颜矿,像睡著了一般寄猩。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上骑疆,一...
    開(kāi)封第一講書(shū)人閱讀 52,821評(píng)論 1 314
  • 那天田篇,我揣著相機(jī)與錄音,去河邊找鬼箍铭。 笑死泊柬,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的诈火。 我是一名探鬼主播兽赁,決...
    沈念sama閱讀 41,236評(píng)論 3 424
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來(lái)了刀崖?” 一聲冷哼從身側(cè)響起惊科,我...
    開(kāi)封第一講書(shū)人閱讀 40,196評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎亮钦,沒(méi)想到半個(gè)月后译断,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,716評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡或悲,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,794評(píng)論 3 343
  • 正文 我和宋清朗相戀三年孙咪,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片巡语。...
    茶點(diǎn)故事閱讀 40,928評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡翎蹈,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出男公,到底是詐尸還是另有隱情荤堪,我是刑警寧澤,帶...
    沈念sama閱讀 36,583評(píng)論 5 351
  • 正文 年R本政府宣布枢赔,位于F島的核電站澄阳,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏踏拜。R本人自食惡果不足惜碎赢,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,264評(píng)論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望速梗。 院中可真熱鬧肮塞,春花似錦、人聲如沸姻锁。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 32,755評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)位隶。三九已至拷窜,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間涧黄,已是汗流浹背篮昧。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,869評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留弓熏,地道東北人恋谭。 一個(gè)月前我還...
    沈念sama閱讀 49,378評(píng)論 3 379
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像挽鞠,于是被迫代替她去往敵國(guó)和親疚颊。 傳聞我的和親對(duì)象是個(gè)殘疾皇子狈孔,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,937評(píng)論 2 361

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