JS: 數據結構與演算法之棧

棧

先來看一道題

Leetcode 32 Longest Valid Parentheses (最長有效括弧)

給定一個只包含 '(' 和 ')' 的字元串，找出最長的包含有效括弧的子串的長度。

示例 1:

輸入: "(()"
輸出: 2
解釋: 最長有效括弧子串為 "()"

示例 2:

輸入: ")()())"
輸出: 4
解釋: 最長有效括弧子串為 "()()"

這道題可以用動態規劃來做，也能用簡潔明瞭的棧來解決。

什麼是棧？

棧是一種先進後出（LIFO）的有序集合，新添加的元素在棧頂，舊元素在棧底。

以下圖為例，1、2、3、4、5、6、7先後進棧：

創建棧

創建一個類來表示棧：

class Stack {
    // 初始化類，創建數組 items 存放入棧元素
    constructor() {
        this.items = [];
    }
    // push 方法進行元素入棧（可同時入棧一或多個元素），無返回值
    push() {
        this.items.push(...arguments);
    }
    // pop 方法出棧一個元素，返回出棧元素
    pop() {
        return this.items.pop();
    }
    // peek 方法返回棧頂元素，不對棧本身做任何操作
    peek() {
        return this.items[this.items.length-1];
    }
    // size 方法返回棧內元素個數
    size() {
        return this.items.length;
    }
    // isEmpty 方法查看棧是否為空，返回布爾值
    isEmpty() {
        return this.items.length == 0;
    }
    // clear 方法清空棧，無返回值
    clear() {
        this.items = [];
    }
    // print 方法列印棧內元素
    print() {
        console.log(this.items.toString());
    }
}

// 測試 
let stack = new Stack();
stack.push(1,2,3,4);
stack.print(); // 1,2,3,4
stack.isEmpty(); // false
stack.size(); // 4
stack.pop(); // 4
stack.peek(); // 3
stack.clear();

註意

因為 JavaScript 的類內暫時無法定義靜態成員，所以可以在類外訪問到存儲棧元素的數組 items，這個操作是很危險的。

stack.items; // [1, 2, 3, 4]

這時可以使用閉包和IIFE進行避免，這是一個很無奈的辦法：

let Stack = (function () {
    // 使用 WeakMap 存儲數組（數組存放進棧元素）
    let items = new WeakMap();
    class Stack {
        constructor() {
            items.set(this, []);
        }
        push() {
            items.get(this).push(...arguments);
        }
        // 其他方法
    }
    return Stack;
})();

let s = new Stack();
// 無法訪問到 items
s.items; // undefined

WeakMap: WeakMap是類似Map的鍵值對集合，但WeakMap的鍵是弱引用的，只要不存在引用，垃圾回收機制就會回收掉占用的記憶體，相當於自動刪除，而不用手動刪除。

用棧解題

思路：

1. 變數start存放有效括弧起始下標，maxLen存放最大長度；
2. 棧只存放左括弧的下標，遇到左括弧，將其下標存入棧中；
3. 遇到右括弧，若此時棧為空，跳過本次迴圈並更新start；若棧不為空，則棧頂元素出棧；
4. 棧頂元素出棧後，若棧為空，則計算當前下標和start的距離，並更新maxLen；
5. 棧頂元素出棧後，若棧不為空，則計算當前下標和棧頂存放的下標的距離，並更新maxLen；
6. 迴圈遍歷直至結束。

function test(str) {
    let stack = new Stack();
    let start = 0;
    let maxLen = 0;

    for(let i=0; i<str.length; i++) {
        // 如果是左括弧，下標入棧
        if (str[i] == '(') {
            stack.push(i);
        } else {
            // 如果是右括弧
            /* 棧內為空，說明本次有效括弧匹配已結束，跳過本次迴圈並更新 start */
            if (stack.isEmpty()) {
                start = i+1;
                continue;
            } else {
                // 棧內不為空，則出棧一個左括弧進行匹配
                stack.pop();
                // 棧頂元素出棧後，棧為空
                if (stack.isEmpty()) {
                    // 根據當前下標和 start 去更新 maxLen
                    maxLen = Math.max(maxLen, i-start+1);
                } else {
                    // 棧不為空，根據當前下標和棧頂存放的下標去更新 maxLen
                    maxLen = Math.max(maxLen, i-stack.peek());
                }
                
            }
        }       
    }
    
    return maxLen;
}

test('(()'); // 2
test(')()())'); // 4

備註

終於從大半個月的考試和課設中解放出來了，每天早起晚睡，還是很累的。