當我開始解LeetCode的問題時，每個問題都像是一個全新的世界。我花了些時間才意識到，大多數問題是按結構分類的，而且如果你認識到模式，問題就會自動分解。今天輪到堆疊了。
在前一篇文章中，我們看到了堆疊是如何運作的。今天我們基於這個基礎來解決三個經典問題。
您將會找到：
- 三個逐步解決的問題：平衡括號、反轉字串和簡化路徑
- 堆疊在面試之外的應用場景
快速提醒
LIFO：後進先出。push添加到頂部，pop超越極限。在 JavaScript 中，陣列已經像堆疊一樣運作。如果你需要完整的細節，它就在那裡。上一篇文章.
我們來談談問題。
問題 1：平衡括號
問題：給定一個字串s僅僅()[]{}，判斷其是否有效。每個開啟都必須有其對應的關閉，並且順序正確.
範例
Input: "()[]{}" → true
Input: "([)]" → false
Input: "{[]}" → true
我們是如何思考的？
"最後開啟的是最先應該關閉的。"這正是堆疊（stack）擅長做的事情。
我們遍歷這個字串。每個開啟符號都會進入堆疊。每個關閉符號必須與堆疊頂部的符號匹配。如果最後堆疊變空，那麼所有符號都關閉得很好.
解決方案
function validParentheses(s) {
const stack = [];
const pairs = { ")": "(", "}": "{", "]": "[" };
for (const char of s) {
if (char === "(" || char === "{" || char === "[") {
stack.push(char);
} else if (stack.pop() !== pairs[char]) {
return false;
}
}
return stack.length === 0;
}
重要的是：
-
pairs將每個關閉符號映射到它的開啟符號. - 開啟符號進入堆疊。關閉符號進行
pop驗證。 - 若在執行
pop時堆疊為空，則回傳undefined且比較失敗。好，這樣我們就不需要額外的檢查了。 - 最終，堆疊必須為空。
複雜度：時間複雜度為O(n)和空間複雜度為O(n)。
問題 2：反轉字串 (簡單)
來自LeetCode的"Reverse String"的變體。 我們要使用堆疊來反轉一個字串.
問題：給定一個字串s，返回反轉的字串.
範例
Input: "stack" → "kcats"
Input: "hello" → "olleh"
我們該如何思考？
"反轉"是關鍵。你按順序放入元素，再按相反順序取出元素。這正是堆疊的功能。
在現實生活中你會用s.split("").reverse().join("")準備好了。這裡我們使用 stack 來觀察模式在實際操作中的應用。
解決方案
var reverseString = function (s) {
const stack = [...s]; // crea un stack con los caracteres
let reversed = "";
while (stack.length > 0) {
reversed += stack.pop();
}
return reversed;
};
我們將所有字元放入堆疊中，然後逐一取出。像pop回傳最後進入的，字元顯示是反的。
複雜度：O(n) 時間和 O(n) 空間.
問題 3: 簡化路徑 (中等)
問題：給定一個 Unix 的絕對路徑，將其轉換為其標準形式.
規則：
-
.代表當前目錄. -
..代表向上移動一級. -
//被視為/。 - 結果並非結束於
/，除非是根目錄.
範例
Input: "/home//foo/" → "/home/foo"
Input: "/../" → "/"
Input: "/a/./b/../../c/" → "/c"
我們是如何思考的？
..是什麼做的？它將我們返回到上一個目錄。那裡有信號，我們需要記住我們是如何通過的，並能夠返回.
我們將路徑分割成/ 我們遍歷每個元件：
-
""或"."，忽略。 -
".."，從堆疊中取出頂端。 - 任何其他東西都是目錄，並放入堆疊。
最後，堆疊包含簡化路徑的目錄。
解決方案
var simplifyPath = function (path) {
const stack = [];
for (const part of path.split("/")) {
if (part === "" || part === ".") continue;
if (part === "..") stack.pop();
else stack.push(part);
}
return "/" + stack.join("/");
};
提示：在 JavaScript 中，pop 在一個空的堆疊上不會破壞任何東西，僅僅返回 undefined。所以如果路徑嘗試超出根目錄，就不需要額外的驗證。
複雜度：時間複雜度為 O(n) 和空間複雜度為 O(n)。
三者背後的模式
如果你連續閱讀它們，會發現它們都是一樣的。三個都解決了同樣的根本問題，就是能夠回到某個先前的地方.
- 平衡括號：記住最後一個開啟的括號來驗證關閉括號.
- 反轉字串：回到相反的順序.
- 簡化路徑：
..回退一級。
這就是堆疊的 суперсила。當一個問題要求你記住最後的操作、撤銷某個動作或從後往前處理時，幾乎總是堆疊的答案。
堆疊不只是面試
堆疊不只是面試的瑣事。 "返回"的模式到處都是：
- 瀏覽器的返回按鈕就是一個堆疊。
- 你的編輯器的撤銷/重做也是。
- 程式語言的堆疊記錄（因此存在堆疊溢出錯誤）。
- 需要維持最後所見上下文的數據管道。
為了持續練習
LeetCode 按難度排序的問題：
- Min Stack，簡單題。
- Baseball Game，簡單題。
- 評估逆波蘭表示法，中等.
- 每日溫度，中等。它是單調堆疊模式的引言.
哪個讓你更難？在評論中告訴我。對我來說Simplify Path讓我花費更多時間來解決它。