Skip to content

1. 先区分三种顺序 ​

先读数据结构基础。栈按后进先出取元素,队列按先进先出取元素,优先队列则按优先级,三者不能互换。数组只是实现载体,不会自动决定使用哪种顺序。

本文主线是括号栈与普通队列;单调栈放到主线稳定之后选学。

2. 括号匹配:最近打开的先关闭 ​

输入只允许包含 ()[]{},遇到其他字符返回 false,空串返回 true。朴素方法反复删除相邻匹配括号会重复扫描;栈保存还没有关闭的左括号,每个右括号必须匹配栈顶。

js
function isValidBrackets(text) {
    const expected = new Map([[')', '('], [']', '['], ['}', '{']]);
    const stack = [];
    for (const char of text) {
        if (char === '(' || char === '[' || char === '{') stack.push(char);
        else if (!expected.has(char) || stack.pop() !== expected.get(char)) return false;
    }
    return stack.length === 0;
}

遍历前缀时,栈从底到顶保存该前缀中尚未关闭的括号。([)] 虽然各种括号数量相等,但嵌套顺序错误,所以只计数不够。每个字符进出栈至多一次,时间为 O(n),辅助空间最坏为 O(n)。

3. 队列:用读取下标避免头部移动 ​

下面队列只接收非 undefined 的值,空队列取出返回 undefined。该约定把“队列为空”与有效数据区分开;实际业务若允许 undefined,需要另行设计返回契约。

js
class Queue {
    // shortcut: 未清空时槽位持续增长,长期队列应改用循环缓冲区。
    constructor() { this.items = []; this.head = 0; }
    get size() { return this.items.length - this.head; }
    enqueue(value) {
        if (value === undefined) throw new TypeError('undefined is reserved for an empty queue');
        this.items.push(value);
    }
    dequeue() {
        if (this.size === 0) return undefined;
        const value = this.items[this.head];
        this.items[this.head++] = undefined;
        if (this.head === this.items.length) {
            this.items = [];
            this.head = 0;
        }
        return value;
    }
}

入队追加到末尾,出队只增加读取下标,并释放已读元素的引用;队列清空时重置数组。按常见动态数组成本模型,入队均摊常数时间,出队常数时间,但底层垃圾回收的实际耗时不属于这个模型。

这个实现适合有限批次的学习任务。队列长期不清空时,已用下标仍然增长,数组槽位占用不等于当前队列长度;空间按自上次清空后累计入队数量计算。长期服务可使用循环缓冲区复用槽位,必须另行处理容量、满/空判断和扩容;不要把简化教学队列当作无限运行的消息队列。

树的层序遍历与图的广度搜索见遍历专题。练习时先手推入队 1、2,取出一次,再入队 3,最终顺序应为 1、2、3。

4. 选学:单调栈解决每日温度 ​

给定有限数值数组,返回每一天到下一次严格更高温度的等待天数,没有则为零;不修改输入。

朴素方法对每一天向后查找,最坏为 O(n²)。优化时保存还没有找到更暖日子的下标;栈中温度从底到顶非递增。新温度更高时,就能为栈顶确定最早答案,因为此前经过的日期都未能使它出栈。

js
function dailyTemperatures(temperatures) {
    const answer = new Array(temperatures.length).fill(0);
    const stack = [];
    for (let i = 0; i < temperatures.length; i++) {
        while (stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) {
            const previous = stack.pop();
            answer[previous] = i - previous;
        }
        stack.push(i);
    }
    return answer;
}

相等温度不能出栈。每个下标入栈一次、出栈至多一次,因此虽然有嵌套循环,总时间仍为 O(n),辅助栈最坏为 O(n),结果数组另外占 O(n)。

手推 [30, 30, 31],期望 [2, 1, 0]。若把比较改为大于等于,第一天会错误地认为第二天更暖。这里保存下标而不是值,因为答案需要日期距离。

5. 验收 ​

sh
node --test tests/algorithm-structures-examples.test.mjs

检查括号的错误嵌套、未关闭和额外右括号;检查队列空取、交错入出与重新使用;温度题用直接向后扫描对照重复、下降、上升和空输入。

先闭卷写括号匹配,再解释队列的空间限制。单调栈是后续选学,不必为了完成第一阶段提前背模板。

评论

正在加载评论…