前端算法系統(tǒng)練習(xí): 棧和隊(duì)列篇

這是前端算法系統(tǒng)練習(xí)系列的第二篇——棧和隊(duì)列篇。關(guān)于為什么要練習(xí)算法和數(shù)據(jù)結(jié)構(gòu)，請(qǐng)見上一篇前端算法系統(tǒng)練習(xí): 鏈表篇完結(jié)。我一直秉承學(xué)習(xí)這件事情一定要系統(tǒng)的觀念，因此每次更新都是一個(gè)完整的專題，雖然比較長，但是看下來結(jié)構(gòu)會(huì)很清晰，收獲的是一塊完整的知識(shí)和方法論。希望對(duì)你能有幫助！

棧&遞歸

有效括號(hào)

給定一個(gè)只包括 '('，')'，'{'，'}'，'['，']'?的字符串，判斷字符串是否有效。

有效字符串需滿足：

左括號(hào)必須用相同類型的右括號(hào)閉合。左括號(hào)必須以正確的順序閉合。注意空字符串可被認(rèn)為是有效字符串。

示例:

輸入:?"()"
輸出:?true

來源: LeetCode第20題

代碼實(shí)現(xiàn)

/**
?*?@param?{string}?s
?*?@return?{boolean}
?*/
var?isValid?=?function(s)?{
????let?stack?=?[];
????for(let?i?=?0;?i?????????let?ch?=?s.charAt(i);
????????if(ch?==?'('?||?ch?==?'['?||?ch?==?'{')?
????????????stack.push(ch);
????????if(!stack.length)?return?false;
????????if(ch?==?')'?&&?stack.pop()?!==?'(')?return?false;
????????if(ch?==?']'?&&?stack.pop()?!==?'['?)?return?false;
????????if(ch?==?'}'?&&?stack.pop()?!==?'{')?return?false;
????}
????return?stack.length?===?0;
};

多維數(shù)組 flatten

將多維數(shù)組轉(zhuǎn)化為一維數(shù)組。

示例:

[1,?[2,?[3,?[4,?5]]],?6]?->?[1,?2,?3,?4,?5,?6]

代碼實(shí)現(xiàn)

/**
?*?@constructor
?*?@param?{NestedInteger[]}?nestedList
?*?@return?{Integer[]}
?*/
let?flatten?=?(nestedList)?=>?{
????let?result?=?[];
????let?fn?=?function?(target,?ary)?{
????????for?(let?i?=?0;?i?????????????let?item?=?ary[i];
????????????if?(Array.isArray(ary[i]))?{
????????????????fn(target,?item);
????????????}?else?{
????????????????target.push(item);
????????????}
????????}
????}
????fn(result,?nestedList)
????return?result;

同時(shí)可采用 reduce 的方式, 一行就可以解決，非常簡潔。

let?flatten?=?(nestedList)?=>??nestedList.reduce((pre,?cur)?=>?pre.concat(Array.isArray(cur)???flatten(cur):?cur),?[])

二叉樹層序遍歷

二叉樹的層序遍歷本是下一章的內(nèi)容，但是其中隊(duì)列的性質(zhì)又體現(xiàn)得太明顯，因此就以這樣一類問題來讓大家練習(xí)隊(duì)列的相關(guān)操作。這里會(huì)不僅僅涉及到普通的層序遍歷, 而且涉及到變形問題，讓大家徹底掌握。

普通的層次遍歷

給定一個(gè)二叉樹，返回其按層次遍歷的節(jié)點(diǎn)值。（即逐層地，從左到右訪問所有節(jié)點(diǎn)）。

示例:

??3
??/?\
9??20
??/??\
??15???7

結(jié)果應(yīng)輸出:

[
??[3],
??[9,20],
??[15,7]
]

來源: LeetCode第102題

實(shí)現(xiàn)

/**
?*?@param?{TreeNode}?root
?*?@return?{number[][]}
?*/
var?levelOrder?=?function(root)?{
????if(!root)?return?[];
????let?queue?=?[];
????let?res?=?[];
????let?level?=?0;
????queue.push(root);
????let?temp;
????while(queue.length)?{
????????res.push([]);
????????let?size?=?queue.length;
????????//?注意一下:?size?--?在層次遍歷中是一個(gè)非常重要的技巧
????????while(size?--)?{
????????????//?出隊(duì)
????????????let?front?=?queue.shift();
????????????res[level].push(front.val);
????????????//?入隊(duì)
????????????if(front.left)?queue.push(front.left);
????????????if(front.right)?queue.push(front.right);
????????}????????
????????level++;
????}
????return?res;
};

二叉樹的鋸齒形層次遍歷

給定一個(gè)二叉樹，返回其節(jié)點(diǎn)值的鋸齒形層次遍歷。（即先從左往右，再從右往左進(jìn)行下一層遍歷，以此類推，層與層之間交替進(jìn)行）。

例如：

給定二叉樹 [3,9,20,null,null,15,7], 輸出應(yīng)如下:

????3
???/?\
??9??20
????/??\
???15???7

返回鋸齒形層次遍歷如下：

[
??[3],
??[20,9],
??[15,7]
]

來源: LeetCode第103題

思路

這一題思路稍微不同，但如果把握住層次遍歷的思路，就會(huì)非常簡單。

代碼實(shí)現(xiàn)

var?zigzagLevelOrder?=?function(root)?{
????if(!root)?return?[];
????let?queue?=?[];
????let?res?=?[];
????let?level?=?0;
????queue.push(root);
????let?temp;
????while(queue.length)?{
????????res.push([]);
????????let?size?=?queue.length;
????????while(size?--)?{
????????????//?出隊(duì)
????????????let?front?=?queue.shift();
????????????res[level].push(front.val);
????????????if(front.left)?queue.push(front.left);
????????????if(front.right)?queue.push(front.right);
????????}??
????????//?僅僅增加下面一行代碼即可
????????if(level?%?2)?res[level].reverse();??????
????????level++;
????}
????return?res;
};

二叉樹的右視圖

給定一棵二叉樹，想象自己站在它的右側(cè)，按照從頂部到底部的順序，返回從右側(cè)所能看到的節(jié)點(diǎn)值。

示例:

輸入:?[1,2,3,null,5,null,4]
輸出:?[1,?3,?4]
解釋:

???1????????????<---
?/???\
2?????3?????????<---
?\?????\
??5?????4???????<---

來源: LeetCode第199題

思路

右視圖？如果你以 DFS 即深度優(yōu)先搜索的思路來想，你會(huì)感覺異常的痛苦。沒錯(cuò)，當(dāng)初我就是這樣被坑的:）

但如果用廣度優(yōu)先搜索的思想，即用層序遍歷的方式，求解這道題目也變得輕而易舉。

代碼實(shí)現(xiàn)

/**
?*?@param?{TreeNode}?root
?*?@return?{number[]}
?*/
var?rightSideView?=?function(root)?{
????if(!root)?return?[];
????let?queue?=?[];
????let?res?=?[];
????queue.push(root);
????while(queue.length)?{
????????res.push(queue[0].val);
????????let?size?=?queue.length;
????????while(size?--)?{
????????????//?一個(gè)size的循環(huán)就是一層的遍歷，在這一層只拿最右邊的結(jié)點(diǎn)
????????????let?front?=?queue.shift();
????????????if(front.right)?queue.push(front.right);
????????????if(front.left)?queue.push(front.left);
????????}
????}
????return?res;
};

無權(quán)圖 BFS 遍歷

完全平方數(shù)

給定正整數(shù) n，找到若干個(gè)完全平方數(shù)（比如 1, 4, 9, 16, ...）使得它們的和等于 n。你需要讓組成和的完全平方數(shù)的個(gè)數(shù)最少。

示例:

輸入:?n?=?12
輸出:?3?
解釋:?12?=?4?+?4?+?4.

來源: LeetCode第279題

思路

這一題其實(shí)最容易想到的思路是動(dòng)態(tài)規(guī)劃，我們放到后面專門來拆解。實(shí)際上用隊(duì)列進(jìn)行圖的建模，也是可以順利地用廣度優(yōu)先遍歷的方式解決的。

看到這個(gè)圖，你可能會(huì)有點(diǎn)懵，我稍微解釋一下你就明白了。

在這個(gè)無權(quán)圖中，每一個(gè)點(diǎn)指向的都是它可能經(jīng)過的上一個(gè)節(jié)點(diǎn)。舉例來說，對(duì) 5 而言，可能是 4 加上了1的平方轉(zhuǎn)換而來，也可能是1 加上了2的平方轉(zhuǎn)換而來，因此跟1和2都有聯(lián)系，依次類推。

那么我們現(xiàn)在要做了就是尋找到從 n 轉(zhuǎn)換到 0 最短的連線數(shù)。

舉個(gè)例子， n = 8 時(shí)，我們需要找到它的鄰居節(jié)點(diǎn)4和7，此時(shí)到達(dá) 4 和到達(dá) 7 的步數(shù)都為 1, 然后分別從 4 和 7 出發(fā)，4 找到鄰居節(jié)點(diǎn)3和0，達(dá)到 3 和 0 的步數(shù)都為 2，考慮到此時(shí)已經(jīng)到達(dá) 0，遍歷終止，返回到達(dá) 0 的步數(shù) 2 即可。

Talk is cheap, show me your code. 我們接下來來一步步實(shí)現(xiàn)這個(gè)尋找的過程。

實(shí)現(xiàn)

接下來我們來實(shí)現(xiàn)第一版的代碼。

/**
?*?@param?{number}?n
?*?@return?{number}
?*/
var?numSquares?=?function(n)?{
????let?queue?=?[];
????queue.push([n,?0]);
????while(queue.length)?{
????????let?[num,?step]?=?queue.shift();
????????for(let?i?=?1;?;?i?++)?{
????????????let?nextNum?=?num?-?i?*?i;
????????????if(nextNum?0)?break;
????????????//?還差最后一步就到了，直接返回?step?+?1
????????????if(nextNum?==?0)?return?step?+?1;
????????????queue.push([nextNum,?step?+?1]);
????????}
????}
????//?最后是不需要返回另外的值的，因?yàn)?1?也是完全平方數(shù)，所有的數(shù)都能用?1?來組合
};

這個(gè)解法從功能上來講是沒有問題的，但是其中隱藏了巨大的性能問題，你可以去LeetCode去測試一下，基本是超時(shí)。

那為什么會(huì)出現(xiàn)這樣的問題？

出就出在這樣一行代碼:

queue.push([nextNum,?step?+?1]);

只要是大于 0 的數(shù)，統(tǒng)統(tǒng)塞進(jìn)隊(duì)列。要知道 2 - 1 = 1， 5 - 4 = 1， 9 - 8 = 1 ......這樣會(huì)重復(fù)非常多的 1, 依次類推，也會(huì)重復(fù)非常多的2,3等等等等。

這樣大量的重復(fù)數(shù)字不僅僅消耗了更多的循環(huán)次數(shù)，同時(shí)也造成更加巨大的內(nèi)存空間壓力。

因此，我們需要對(duì)已經(jīng)推入隊(duì)列的數(shù)字進(jìn)行標(biāo)記，避免重復(fù)推入。改善代碼如下:

var?numSquares?=?function(n)?{
????let?map?=?new?Map();
????let?queue?=?[];
????queue.push([n,?0]);
????map.set(n,?true);
????while(queue.length)?{
????????let?[num,?step]?=?queue.shift();
????????for(let?i?=?1;?;?i++)?{
????????????let?nextNum?=?num?-?i?*?i;
????????????if(nextNum?0)?break;
????????????if(nextNum?==?0)?return?step?+?1;
????????????//?nextNum?未被訪問過
????????????if(!map.get(nextNum)){
????????????????queue.push([nextNum,?step?+?1]);
????????????????//?標(biāo)記已經(jīng)訪問過
????????????????map.set(nextNum,?true);
????????????}
????????}
????}
};

單詞接龍

給定兩個(gè)單詞（beginWord 和 endWord）和一個(gè)字典，找到從 beginWord 到 endWord 的最短轉(zhuǎn)換序列的長度。轉(zhuǎn)換需遵循如下規(guī)則：

• 每次轉(zhuǎn)換只能改變一個(gè)字母。
• 轉(zhuǎn)換過程中的中間單詞必須是字典中的單詞。

說明:

1. 如果不存在這樣的轉(zhuǎn)換序列，返回 0。
2. 所有單詞具有相同的長度。
3. 所有單詞只由小寫字母組成。
4. 字典中不存在重復(fù)的單詞。
5. 你可以假設(shè) beginWord 和 endWord 是非空的，且二者不相同。

示例:

輸入:
beginWord?=?"hit",
endWord?=?"cog",
wordList?=?["hot","dot","dog","lot","log","cog"]

輸出:?5

解釋:?一個(gè)最短轉(zhuǎn)換序列是?"hit"?->?"hot"?->?"dot"?->?"dog"?->?"cog",
?????返回它的長度 5。

來源: LeetCode第127題

思路

這一題是一個(gè)更加典型的用圖建模的問題。如果每一個(gè)單詞都是一個(gè)節(jié)點(diǎn)，那么只要和這個(gè)單詞僅有一個(gè)字母不同，那么就是它的相鄰節(jié)點(diǎn)。

這里我們可以通過 BFS 的方式來進(jìn)行遍歷。實(shí)現(xiàn)如下:

代碼實(shí)現(xiàn)

/**
?*?@param?{string}?beginWord
?*?@param?{string}?endWord
?*?@param?{string[]}?wordList
?*?@return?{number}
?*/
var?ladderLength?=?function(beginWord,?endWord,?wordList)?{
????//?兩個(gè)單詞在圖中是否相鄰
????const?isSimilar?=?(a,?b)?=>?{
????????let?diff?=?0
????????for(let?i?=?0;?i?????????????if(a.charAt(i)?!==?b.charAt(i))?diff++;
????????????if(diff?>?1)?return?false;?
????????}
????????return?true;
????}
????let?queue?=?[beginWord];
????let?index?=?wordList.indexOf(beginWord);
????if(index?!==?-1)?wordList.splice(index,?1);
????let?res?=?2;
????while(queue.length)?{
????????let?size?=?queue.length;
????????while(size?--)?{
????????????let?front?=?queue.shift();
????????????for(let?i?=?0;?i?????????????????if(!isSimilar(front,?wordList[i]))continue;
????????????????//?找到了
????????????????if(wordList[i]?===?endWord)?{
????????????????????return?res;
????????????????}
????????????????else?{
????????????????????queue.push(wordList[i]);
????????????????}
????????????????//?wordList[i]已經(jīng)成功推入，現(xiàn)在不需要了，刪除即可
????????????????//?這一步性能優(yōu)化，相當(dāng)關(guān)鍵，不然100%超時(shí)
????????????????wordList.splice(i,?1);
????????????????i?--;
????????????}
????????}
????????//?步數(shù)?+1
????????res?+=?1;
????}
????return?0;
};

實(shí)現(xiàn)優(yōu)先隊(duì)列

所謂優(yōu)先隊(duì)列，就是一種特殊的隊(duì)列, 其底層使用堆的結(jié)構(gòu)，使得每次添加或者刪除，讓隊(duì)首元素始終是優(yōu)先級(jí)最高的。關(guān)于優(yōu)先級(jí)通過什么字段、按照什么樣的比較方式來設(shè)定，可以由我們自己來決定。

要實(shí)現(xiàn)優(yōu)先隊(duì)列，首先來實(shí)現(xiàn)一個(gè)堆的結(jié)構(gòu)。

關(guān)于堆的說明

可能你以前沒有接觸過堆這種數(shù)據(jù)結(jié)構(gòu)，但是其實(shí)是很簡單的一種結(jié)構(gòu)，其本質(zhì)就是一棵二叉樹。但是這棵二叉樹比較特殊，除了用數(shù)組來依次存儲(chǔ)各個(gè)節(jié)點(diǎn)(節(jié)點(diǎn)對(duì)應(yīng)的數(shù)組下標(biāo)和層序遍歷的序號(hào)一致)之外，它需要保證任何一個(gè)父節(jié)點(diǎn)的優(yōu)先級(jí)大于子節(jié)點(diǎn)，這也是它最關(guān)鍵的性質(zhì)，因?yàn)楸ＷC了根元素一定是優(yōu)先級(jí)最高的。

舉一個(gè)例子:

現(xiàn)在這個(gè)堆的數(shù)組就是: [10, 7, 2, 5, 1]

因此也會(huì)產(chǎn)生兩個(gè)非常關(guān)鍵的操作——siftUp 和 siftDown。

對(duì)于siftUp操作，我們?cè)囅胍幌卢F(xiàn)在有一個(gè)正常的堆，滿足任何父元素優(yōu)先級(jí)大于子元素，這時(shí)候向這個(gè)堆的數(shù)組末尾又添加了一個(gè)元素，那現(xiàn)在可能就不符合堆的結(jié)構(gòu)特點(diǎn)了。那么現(xiàn)在我將新增的節(jié)點(diǎn)和其父節(jié)點(diǎn)進(jìn)行比較，如果父節(jié)點(diǎn)優(yōu)先級(jí)小于它，則兩者交換，不斷向上比較直到根節(jié)點(diǎn)為止，這樣就保證了堆的正確結(jié)構(gòu)。而這樣的操作就是siftUp。

siftDown是與其相反方向的操作，從上到下比較，原理相同，也是為了保證堆的正確結(jié)構(gòu)。

實(shí)現(xiàn)一個(gè)最大堆

最大堆，即堆頂元素為優(yōu)先級(jí)最高的元素。

//?以最大堆為例來實(shí)現(xiàn)一波
/**
*?@param?{number[]}?nums
*?@param?{number}?k
*?@return?{number[]}
*/
class?MaxHeap?{
??constructor(arr?=?[],?compare?=?null)?{
????this.data?=?arr;
????this.size?=?arr.length;
????this.compare?=?compare;
??}
??getSize()?{
????return?this.size;
??}
??isEmpty()?{
????return?this.size?===?0;
??}
??//?增加元素
??add(value)?{
????this.data.push(value);
????this.size++;
????//?增加的時(shí)候把添加的元素進(jìn)行?siftUp
????this._siftUp(this.getSize()?-?1);
??}
??//?找到優(yōu)先級(jí)最高的元素
??findMax()?{
????if?(this.getSize()?===?0)
??????return;
????return?this.data[0];
??}
??//?讓優(yōu)先級(jí)最高的元素(即隊(duì)首元素)出隊(duì)
??extractMax()?{
????//?1.保存隊(duì)首元素
????let?ret?=?this.findMax();
????//?2.讓隊(duì)首和隊(duì)尾元素交換位置
????this._swap(0,?this.getSize()?-?1);
????//?3.?把隊(duì)尾踢出去，size--
????this.data.pop();
????this.size--;
????//?4.?新的隊(duì)首?siftDown
????this._siftDown(0);
????return?ret;
??}

??toString()?{
????console.log(this.data);
??}
??_swap(i,?j)?{
????[this.data[i],?this.data[j]]?=?[this.data[j],?this.data[i]];
??}
??_parent(index)?{
????return?Math.floor((index?-?1)?/?2);
??}
??_leftChild(index)?{
????return?2?*?index?+?1;
??}
??_rightChild(index)?{
????return?2?*?index?+?2;
??}
??_siftUp(k)?{
????//?上浮操作，只要子元素優(yōu)先級(jí)比父節(jié)點(diǎn)大，父子交換位置，一直向上直到根節(jié)點(diǎn)
????while?(k?>?0?&&?this.compare(this.data[k],?this.data[this._parent(k)]))?{
??????this._swap(k,?this._parent(k));
??????k?=?this._parent(k);
????}
??}
??_siftDown(k)?{
????//?存在左孩子的時(shí)候
????while?(this._leftChild(k)?this.size)?{
??????let?j?=?this._leftChild(k);
??????//?存在右孩子而且右孩子比左孩子大
??????if?(this._rightChild(k)?this.size?&&
????????this.compare(this.data[this._rightChild(k)],?this.data[j]))?{
????????j++;
??????}
??????if?(this.compare(this.data[k],?this.data[j]))
????????return;
??????//?父節(jié)點(diǎn)比子節(jié)點(diǎn)小，交換位置
??????this._swap(k,?j);
??????//?繼續(xù)下沉
??????k?=?j;
????}
??}
}

實(shí)現(xiàn)優(yōu)先隊(duì)列

有了最大堆作鋪墊，實(shí)現(xiàn)優(yōu)先隊(duì)列就易如反掌，廢話不多說，直接放上代碼。

class?PriorityQueue?{
??//?max?為優(yōu)先隊(duì)列的容量
??constructor(max,?compare)?{
????this.max?=?max;
????this.compare?=?compare;
????this.maxHeap?=?new?MaxHeap([],?compare);
??}

??getSize()?{
????return?this.maxHeap.getSize();
??}

??isEmpty()?{
????return?this.maxHeap.isEmpty();
??}

??getFront()?{
????return?this.maxHeap.findMax();
??}

??enqueue(e)?{
????//?比當(dāng)前最高的優(yōu)先級(jí)的還要高，直接不處理
????if?(this.getSize()?===?this.max)?{
??????if?(this.compare(e,?this.getFront()))?return;
??????this.dequeue();
????}
????return?this.maxHeap.add(e);
??}

??dequeue()?{
????if?(this.getSize()?===?0)?return?null;
????return?this.maxHeap.extractMax();
??}
}

怎么樣，是不是非常簡單？傳說中的優(yōu)先隊(duì)列也不過如此。

且慢，可能會(huì)有人問: 你怎么保證這個(gè)優(yōu)先隊(duì)列是正確的呢?

我們不妨來做一下測試:

let?pq?=?new?PriorityQueue(3);
pq.enqueue(1);
pq.enqueue(333);
console.log(pq.dequeue());
console.log(pq.dequeue());
pq.enqueue(3);
pq.enqueue(6);
pq.enqueue(62);
console.log(pq.dequeue());
console.log(pq.dequeue());
console.log(pq.dequeue());

結(jié)果如下:

333
1
62
6
3

可見，這個(gè)優(yōu)先隊(duì)列的功能初步滿足了我們的預(yù)期。后面，我們將通過實(shí)際的例子來運(yùn)用這種數(shù)據(jù)結(jié)構(gòu)來解決問題。

優(yōu)先隊(duì)列應(yīng)用

前 K 個(gè)高頻元素

給定一個(gè)非空的整數(shù)數(shù)組，返回其中出現(xiàn)頻率前 k 高的元素。

示例:

輸入:?nums?=?[1,1,1,2,2,3],?k?=?2
輸出:?[1,2]

說明:

• 你可以假設(shè)給定的 k 總是合理的，且 1 ≤ k ≤ 數(shù)組中不相同的元素的個(gè)數(shù)。
• 你的算法的時(shí)間復(fù)雜度必須優(yōu)于 O(n log n) , n 是數(shù)組的大小。

來源: LeetCode第347題

思路

首先要做的肯定是統(tǒng)計(jì)頻率，那之后如何來選取頻率前 K 個(gè)元素同時(shí)又保證時(shí)間復(fù)雜度小于 O(n log n)呢？

當(dāng)然，這是一道典型的考察優(yōu)先隊(duì)列的題，利用容量為 K 的優(yōu)先隊(duì)列每次踢出不符合條件的值，那么最后剩下的即為所求。整個(gè)時(shí)間復(fù)雜度成為 O（n log K），明顯是小于 O(n log n) 的。

既然是優(yōu)先隊(duì)列，就涉及到如何來定義優(yōu)先級(jí)的問題。

倘若我們以高頻率為高優(yōu)先級(jí)，那么隊(duì)首始終是高頻率的元素，因此每次出隊(duì)是踢出出現(xiàn)頻率最高的元素，假設(shè)優(yōu)先隊(duì)列容量為 K，那照這么做，剩下的是頻率最低的 K 個(gè)元素，顯然不符合題意。

因此，我們需要的是每次出隊(duì)時(shí)踢出頻率最低的元素，這樣最后剩下來的就是頻率最高 K 個(gè)元素。

是不是我們?yōu)榱颂叱?strong>頻率最低的元素，還要重新寫一個(gè)小頂堆的實(shí)現(xiàn)呢？

完全不需要！就像我剛才所說的，合理地定義這個(gè)優(yōu)先級(jí)的比較邏輯即可。接下來我們來具體實(shí)現(xiàn)一下。

代碼實(shí)現(xiàn)

var?topKFrequent?=?function(nums,?k)?{
???let?map?=?{};
???let?pq?=?new?PriorityQueue(k,?(a,?b)?=>?map[a]?-?map[b]?0);
???for(let?i?=?0;?i????????if(!map[nums[i]])?map[nums[i]]?=?1;
???????else?map[nums[i]]?=?map[[nums[i]]]?+?1;
???}
???let?arr?=?Array.from(new?Set(nums));
???for(let?i?=?0;?i????????pq.enqueue(arr[i]);
???}
???return?pq.maxHeap.data;
};

合并 K 個(gè)排序鏈表

合并 k 個(gè)排序鏈表，返回合并后的排序鏈表。請(qǐng)分析和描述算法的復(fù)雜度。

示例:

輸入:
[
??1->4->5,
??1->3->4,
??2->6
]
輸出:?1->1->2->3->4->4->5->6

這一題我們之前在鏈表篇實(shí)現(xiàn)過，殊不知，它也可以利用優(yōu)先隊(duì)列完美解決。

來源: LeetCode第23題

/**
?*?@param?{ListNode[]}?lists
?*?@return?{ListNode}
?*/
var?mergeKLists?=?function(lists)?{
????let?dummyHead?=?p?=?new?ListNode();
????//?定義優(yōu)先級(jí)的函數(shù)，重要！
????let?pq?=?new?PriorityQueue(lists.length,?(a,?b)?=>?a.val?<=?b.val);
????//?將頭結(jié)點(diǎn)推入優(yōu)先隊(duì)列
????for(let?i?=?0;?i?????????if(lists[i])?pq.enqueue(lists[i]);
????//?取出值最小的節(jié)點(diǎn)，如果?next?不為空，繼續(xù)推入隊(duì)列
????while(pq.getSize())?{
????????let?min?=?pq.dequeue();
????????p.next?=?min;
????????p?=?p.next;
????????if(min.next)?pq.enqueue(min.next);
????}
????return?dummyHead.next;
};

怎么樣，是不是被驚艷到！原來優(yōu)先隊(duì)列可以這樣來使用！

雙端隊(duì)列及應(yīng)用

什么是雙端隊(duì)列？

雙端隊(duì)列是一種特殊的隊(duì)列，首尾都可以添加或者刪除元素，是一種加強(qiáng)版的隊(duì)列。

JS 中的數(shù)組就是一種典型的雙端隊(duì)列。push、pop 方法分別從尾部添加和刪除元素，unshift、shift 方法分別從首部添加和刪除元素。

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

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

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

示例:

輸入:?nums?=?[1,3,-1,-3,5,3,6,7],?和?k?=?3
輸出:?[3,3,5,5,6,7]?
解釋:?

??滑動(dòng)窗口的位置????????????????最大值
---------------???????????????-----
[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í)間復(fù)雜度應(yīng)為線性。

來源: LeetCode第239題

思路

這是典型地使用雙端隊(duì)列求解的問題。

建立一個(gè)雙端隊(duì)列 window，每次 push 進(jìn)來一個(gè)新的值，就將 window 中目前前面所有比它小的值都刪除。利用雙端隊(duì)列的特性，可以從后往前遍歷，遇到小的就刪除之，否則停止。

這樣可以保證隊(duì)首始終是最大值，因此尋找最大值的時(shí)間復(fù)雜度可以降到 O(1)。由于 window 中會(huì)有越來越多的值被淘汰，因此整體的時(shí)間復(fù)雜度是線性的。

代碼實(shí)現(xiàn)

代碼非常的簡潔，但是如果要寫出 bug free 的代碼還是有相當(dāng)?shù)碾y度的，希望你能自己獨(dú)立實(shí)現(xiàn)一遍。

var?maxSlidingWindow?=?function(nums,?k)?{
????//?異常處理
????if(nums.length?===?0?||?!k)?return?[];
????let?window?=?[],?res?=?[];
????for(let?i?=?0;?i?????????//?先把滑動(dòng)窗口之外的踢出
????????if(window[0]?!==?undefined?&&?window[0]?<=?i?-?k)?window.shift();
????????//?保證隊(duì)首是最大的
????????while(nums[window[window.length?-?1]]?<=?nums[i])??window.pop();
????????window.push(i);
????????if(i?>=?k?-?1)?res.push(nums[window[0]])?
????}
????return?res;
};

棧和隊(duì)列的相互實(shí)現(xiàn)

棧實(shí)現(xiàn)隊(duì)列

使用棧實(shí)現(xiàn)隊(duì)列的下列操作：

push(x) -- 將一個(gè)元素放入隊(duì)列的尾部。pop() -- 從隊(duì)列首部移除元素。peek() -- 返回隊(duì)列首部的元素。empty() -- 返回隊(duì)列是否為空。

示例:

let?queue?=?new?MyQueue();

queue.push(1);
queue.push(2);??
queue.peek();??//?返回?1
queue.pop();???//?返回?1
queue.empty();?//?返回?false

來源: LeetCode第232題

思路

既然棧是先進(jìn)后出, 要想得到先進(jìn)先出的效果，我們不妨用兩個(gè)棧。

當(dāng)進(jìn)行push操作時(shí)，push 到 stack1，而進(jìn)行pop和peek的操作時(shí)，我們通過stack2。

當(dāng)然這其中有一個(gè)特殊情況，就是stack2是空，如何來進(jìn)行pop和peek? 很簡單，把stack1中的元素依次 pop 并推入stack2中，然后正常地操作 stack2即可，如下圖所示:

這就就能保證先入先出的效果了。

代碼實(shí)現(xiàn)

var?MyQueue?=?function()?{
????this.stack1?=?[];
????this.stack2?=?[];
};

MyQueue.prototype.push?=?function(x)?{
????this.stack1.push(x);
};
//?將?stack1?的元素轉(zhuǎn)移到?stack2
MyQueue.prototype.transform?=?function()?{
??while(this.stack1.length)?{
????this.stack2.push(this.stack1.pop());
??}
}

MyQueue.prototype.pop?=?function()?{
??if(!this.stack2.length)?this.transform();
??return?this.stack2.pop();
};

MyQueue.prototype.peek?=?function()?{
????if(!this.stack2.length)?this.transform();
????return?this.stack2[this.stack2.length?-?1];
};

MyQueue.prototype.empty?=?function()?{
????return?!this.stack1.length?&&?!this.stack2.length;
};

隊(duì)列實(shí)現(xiàn)棧

和上一題的效果剛好相反，用隊(duì)列先進(jìn)先出的方式來實(shí)現(xiàn)先進(jìn)后出的效果。

思路

以上面的隊(duì)列為例，push 操作好說，直接從在隊(duì)列末尾推入。但 pop 和 peek 呢？

回到我們的目標(biāo)，我們的目標(biāo)是拿到隊(duì)尾的值，也就是3。這就好辦了，我們讓前面的元素統(tǒng)統(tǒng)出隊(duì)，只留隊(duì)尾元素即可，剩下的元素讓另外一個(gè)隊(duì)列保存。

來源: LeetCode第225題

代碼實(shí)現(xiàn)

實(shí)現(xiàn)過程中，值得注意的一點(diǎn)是，queue1 始終保存前面的元素，queue2 始終保存隊(duì)尾元素（即棧頂元素 ）。

但是當(dāng) push 的時(shí)候有一個(gè)陷阱，就是當(dāng)queue2已經(jīng)有元素的時(shí)候，不能將新值 push 到 queue1，因?yàn)榇藭r(shí)的棧頂元素應(yīng)該更新。此時(shí)對(duì)于新的值來說，應(yīng)先 push 到 queue2， 然后將舊的棧頂從queue2出隊(duì)，推入 queue1，這樣就實(shí)現(xiàn)了更新棧頂的操作。

var?MyStack?=?function()?{
????this.queue1?=?[];
????this.queue2?=?[];
};
MyStack.prototype.push?=?function(x)?{
????if(!this.queue2.length)?this.queue1.push(x);
????else?{
????????//?queue2?已經(jīng)有值
????????this.queue2.push(x);
????????//?舊的棧頂移到?queue1?中
????????this.queue1.push(this.queue2.shift());
????}

};
MyStack.prototype.transform?=?function()?{
????while(this.queue1.length?!==?1)?{
????????this.queue2.push(this.queue1.shift())
????}
????//?queue2?保存了前面的元素
????//?讓?queue1?和?queue2?交換
????//?現(xiàn)在queue1?包含前面的元素，queue2?里面就只包含隊(duì)尾的元素
????let?tmp?=?this.queue1;
????this.queue1?=?this.queue2;
????this.queue2?=?tmp;
}
MyStack.prototype.pop?=?function()?{
????if(!this.queue2.length)?this.transform();
????return?this.queue2.shift();
};
MyStack.prototype.top?=?function()?{
????if(!this.queue2.length)?this.transform();
????return?this.queue2[0];
};
MyStack.prototype.empty?=?function()?{
????return?!this.queue1.length?&&?!this.queue2.length;
};