算法笔记第 04 周

本系列致力于将高频的算法题进行回顾与分析，感兴趣的小伙伴请继续阅读吧。

155. 最小栈

力扣题目链接 (opens new window)

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素val推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。

提示：

• -2^31 <= val <= 2^31 - 1
• pop、top 和 getMin 操作总是在 非空栈 上调用
• push, pop, top, and getMin最多被调用 3 * 10^4 次

思路：

既可以使用辅助栈来维护一个最小值是栈顶的栈，也可以维护一个变量来实时保存最小值。这里采用第二种方式。

当执行入栈操作时，将val和原本的最小值进行比较，较小值便是最新的最小值。当执行出栈操作时，依旧需要实时更新最小值，方法是将栈里剩余的元素展开，比较出最小值。

通过实时维护最小值，便可以在常数时间内获取到当前栈的最小值。

实时替换

var MinStack = function() {
    this.stack = [];
    this.min = Number.MAX_SAFE_INTEGER;
};

/** 
 * @param {number} val
 * @return {void}
 */
MinStack.prototype.push = function(val) {
    this.stack.push(val);
    this.min = Math.min(val, this.min);
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    let val = this.stack.pop();
    this.min = Math.min(...this.stack)
    return val;
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    let length = this.stack.length;
    if (!length) return null;
    return this.stack[length - 1];
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    return this.min;
};

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(val)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */

20. 有效的括号

力扣题目链接 (opens new window)

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。

示例 1：

输入：s = "()[]{}"
输出：true

示例 2：

输入：s = "([)]"
输出：false

提示：

• 1 <= s.length <= 104
• s 仅由括号 '()[]{}' 组成

思路：

本题是经典的栈应用问题。可以借助栈后进先出的特点求解。

维护一个栈用来存放尚未配对的括号。然后依次遍历字符串，如果栈顶元素与当前字符是配对的括号，就将栈顶元素跳出；如果不配对，则将当前字符放入栈顶。

如果最终所有字符括号都配对，栈肯定是空的。如果不配对，则栈不为空。因此判断栈是否为空，就可知晓是否括号配对。

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    let stack = [];
    let map = {
        ')': '(',
        ']': '[',
        '}': '{',
    };
    let length = s.length;
    let idx = 0;
    while(idx < length) {
        let stackLen = stack.length;
        if (!stackLen) {
            stack.push(s[idx++]);
            continue;
        }
        stack[stackLen - 1] === map[s[idx]] ? stack.pop() : stack.push(s[idx]);
        idx++;
    }
    return !stack.length;
};

1047. 删除字符串中的所有相邻重复项

力扣题目链接 (opens new window)

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例1：

输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

提示：

1. 1 <= S.length <= 20000
2. S 仅由小写英文字母组成。

思路：

本题可以使用栈的思路来解决。依次将字符串的字符放入栈中，同时判断栈顶元素是否与当前字符相等，如果相等，则弹出栈顶元素；如果不相等则将当前字符放入栈顶。最终剩下的元素所拼接成的字符串就是没有相邻项的结果。

这里每次循环都弹出一个字符，用来判断与接下来需要比较的字符是否相等，如果相等则全部丢弃，继续判断下一个字符，如果不相等则按照顺序全部放入栈中。

栈

/**
 * @param {string} s
 * @return {string}
 */
var removeDuplicates = function(s) {
    let stack = [];
    let idx = 0;
    while (idx < s.length) {
        const top = stack.pop();
        s[idx] !== top ? stack.push(top, s[idx++]) : idx++;
    }
    return stack.join('')
};

双指针

其实本题还可以使用双指针的思路进行求解。 将字符串分隔为数组，并维护快慢指针。当开始循环时，首先将快指针的元素覆盖到慢指针上。然后判断慢指针的元素和上一个元素是否相同，如果相同，则将慢指针递减，方便下一次循环进行覆盖。如果不相同则慢指针递增。每次循环都需要将快指针不断递增。

也就是说，快指针负责不断往前走获取新的字符，慢指针负责判断相邻元素是否重复，如果重复则丢弃，并在下一次将快指针的元素覆盖到递减过的慢指针元素上，从而继续判断相邻元素是否重复。

最后将数组截取到慢指针所在位置，并拼接为字符串返回即可。

/**
 * @param {string} s
 * @return {string}
 */
var removeDuplicates = function(s) {
    let arr = s.split('');
    let fast = 0;
    let slow = 0;
    while(fast < s.length) {
        arr[slow] = arr[fast];
        if (slow > 0 && arr[slow] === arr[slow - 1]) slow--;
        else slow++;
        fast++;
    }
    return arr.slice(0, slow).join('');
};

总结

本题考查栈的应用，难度系数简单。还需记住栈的特点后进先出。

1209. 删除字符串中的所有相邻重复项 II

给你一个字符串 s，「k 倍重复项删除操作」将会从 s 中选择 k 个相邻且相等的字母，并删除它们，使被删去的字符串的左侧和右侧连在一起。

你需要对 s 重复进行无限次这样的删除操作，直到无法继续为止。

在执行完所有删除操作后，返回最终得到的字符串。

本题答案保证唯一。

示例 1：

输入：s = "deeedbbcccbdaa", k = 3
输出："aa"
解释：
先删除 "eee" 和 "ccc"，得到 "ddbbbdaa"
再删除 "bbb"，得到 "dddaa"
最后删除 "ddd"，得到 "aa"

提示：

• 1 <= s.length <= 10^5
• 2 <= k <= 10^4
• s 中只含有小写英文字母。

思路：

与上一题类似，也是借用栈来求解。不同的是，这里是删除相邻重复k次的项。那么可以这么做：

遍历字符串的每个字符元素，

• 如果栈为空，则直接放入栈中；
• 如果栈顶元素的首项不等于当前元素，那么意味着不重复，则将元素放入栈中；
• 如果栈顶元素的首项等于当前元素，但是栈顶元素字符串的长度小于k - 1，则依旧不构成重复的条件；因为算上当前元素加上k - 1才能达到相邻k项的要求，因此将当前元素拼接到栈顶字符串后面，等待后续元素，如果后续元素刚好等于这个元素，就达到了消除的条件；
• 如果栈顶元素的首项等于当前元素，且满足消除条件，则消除栈顶元素。

需要注意的是，每次遍历都是将栈顶元素弹出进行判断。

/**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
var removeDuplicates = function(s, k) {
    let stack = [];
    let idx = 0;
    while (idx < s.length) {
        const prev = stack.pop();
        if (!prev) { // 栈为空，直接添加
            stack.push(s[idx++]);
            continue;
        }
        if (prev[0] !== s[idx]) stack.push(prev, s[idx++]); // 不是重复元素，继续往栈里添加
        else if (prev.length < k - 1) stack.push(prev + s[idx++]); // 是重复元素，但没达到消除条件
        else idx++; // 满足条件，消除
    }
    return stack.join(''); // 拼接为字符串，并返回
};

239. 滑动窗口最大值

力扣题目链接 (opens new window)

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值

---

[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

提示：

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 1 <= k <= nums.length

思路：

本题与剑指 Offer 59 - I. 滑动窗口的最大值相同，已做过题解，这里直接给出相应代码：

辅助队列

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
    if (!nums.length || !k) return []; // 参数为空数组或者k为0就返回空数组
    let deque = []; // 初始化辅助队列
    let length = nums.length; // 缓存数组长度
    let res = Array.from({ length: length - k + 1 }); // 初始化指定长度的结果数组
    for (let j = 0, i = 1 - k; j < length; i++, j++) {
        if (i > 0 && deque[0] === nums[i - 1]) deque.shift(); // 弹出已经在滑动窗口外的值
        while(deque.length && deque[deque.length - 1] < nums[j]) {
            deque.pop(); // 确保辅助队列递减
        }
        deque.push(nums[j]); // 放入队列末尾
        if (i >= 0) res[i] = deque[0]; // 滑动窗口左侧大于等于0时，将最大值放入结果数组
    }
    return res;
};

380. O(1) 时间插入、删除和获取随机元素

力扣题目链接 (opens new window)

实现RandomizedSet 类：

• RandomizedSet() 初始化 RandomizedSet 对象
• bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
• bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
• int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。

你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。

示例：

输入
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
输出
[null, true, false, true, 2, true, false, 2]

解释
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomizedSet.remove(2); // 返回 false ，表示集合中不存在 2 。
randomizedSet.insert(2); // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomizedSet.getRandom(); // getRandom 应随机返回 1 或 2 。
randomizedSet.remove(1); // 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomizedSet.insert(2); // 2 已在集合中，所以返回 false 。
randomizedSet.getRandom(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2

提示：

• -2^31 <= val <= 2^31 - 1
• 最多调用 insert、remove 和 getRandom 函数 2 * 10^5 次
• 在调用 getRandom 方法时，数据结构中 至少存在一个 元素。

思路：

根据题目要求，需要在O(1)的复杂度内实现增删和获取随机。本题既可以使用散列也可以使用集合来实现。

这里使用集合来实现。由于集合原生提供了添加、删除、判断存在的API，因此增删是很容易实现的。核心是返回随机值。这里可以通过调用Set上的size属性来获取集合的大小，然后随机得到一个大小范围内的下标值，获取随机值并返回即可。

Set

var RandomizedSet = function() {
    this.set = new Set();
};

/** 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.insert = function(val) {
    if (this.set.has(val)) return false;
    this.set.add(val);
    return true;
};

/** 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.remove = function(val) {
    if (!this.set.has(val)) return false;
    this.set.delete(val);
    return true;
};

/**
 * @return {number}
 */
RandomizedSet.prototype.getRandom = function() {
    let random = Math.floor(Math.random() * this.set.size);
    return [...this.set][random];
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * var obj = new RandomizedSet()
 * var param_1 = obj.insert(val)
 * var param_2 = obj.remove(val)
 * var param_3 = obj.getRandom()
 */

我们来依次分析下代码：

1. 插入的逻辑就是按照题目给出的逻辑来处理，存在返回false，不存在添加后返回true。
2. 删除同理。
3. 重点是返回随机的元素，要确保每个元素都是同等概率被返回。这里的做法是使用集合的长度与[0, 1)的随机值进行相乘，并向下取整。这样做之后，结果的范围是[0, length) 。然后将集合展开成数组，并通过随机下标进行访问。因为数组的下标值是[0, length - 1] ，而随机下标刚好是不包括length的，因此可以确保每个值都被随机访问。

总结

本题考查Set集合的特性，难度系数中等。

144. 二叉树的前序遍历

力扣题目链接 (opens new window)

给你二叉树的根节点 root ，返回它节点值的 前序 **遍历。

示例一：

输入：root = [1,null,2,3]
输出：[1,2,3]

提示：

• 树中节点数目在范围 [0, 100] 内
• 100 <= Node.val <= 100

**进阶：**递归算法很简单，你可以通过迭代算法完成吗？

思路：

二叉树的遍历分为前序、中序、后序遍历。这里先解决前序遍历。

先使用递归来求解。前序遍历的顺序是根左右，因此先将当前节点的值放入结果数组中，然后再递归的求出左节点和右节点即可。

递归

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
    let result = [];
    const preOrder = (root) => {
        if (!root) return;
        result.push(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }
    preOrder(root);
    return result;
};

迭代

递归的本质就是调用栈，因此可以使用栈来实现迭代式的前序遍历。

核心思路是：首先将根节点放入栈中，方便后续判断。当栈内有元素就持续循环，每次循环都将栈顶元素弹出，直接放入结果数组中，相当于先遍历了根节点。因为栈的特点是后进先出，所以我们要先将右子节点放入栈中，再将左子节点放入栈中。这样弹出的顺序才是左子节点和右子节点。

由此，达到了前序遍历的目的。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
    let result = [];
    let stack = [];
    if (root) stack.push(root);
    while(stack.length) {
        const root = stack.pop();
        result.push(root.val);
        if (root.right) stack.push(root.right);
        if (root.left) stack.push(root.left);
    }
    return result;
};

总结

这里分别采用了递归和迭代的方式来实现前序遍历。递归的思路很好理解，这里需要重点掌握迭代的方式。而迭代的核心思想跟递归是类似的，因为递归就是调用栈。因此迭代是采用了栈来实现前序遍历。由于栈的特点是后进先出，因此需要注意放入左右子节点的顺序，保证弹出顺序是正确的。

94. 二叉树的中序遍历

力扣题目链接 (opens new window)

给定一个二叉树的根节点 root ，返回它的 中序 遍历。

示例1：

输入：root = [1,null,2,3]
输出：[1,3,2]

提示：

• 树中节点数目在范围 [0, 100] 内
• 100 <= Node.val <= 100

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

思路：

与前序遍历类似，我们先使用递归求解，再来使用迭代求解。

递归

递归方式整体思路都是类似的，唯一不同的地方在于将节点放入结果数组的时机。需要跟前中后的顺序对应起来。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    let result = [];
    const inOrder = (root) => {
        if (!root) return;
        inOrder(root.left);
        result.push(root.val);
        inOrder(root.right);
    }
    inOrder(root);
    return result;
};

迭代

重点来看迭代方式的实现。中序遍历的顺序是左根右。因此我们要想办法先找到最左侧的子节点。这里依旧使用栈来实现。我们需要朝着左侧方向一条道走到黑，直到左子节点没有左子节点为止。寻找左子节点的途中，将经过的节点放入栈中。当没有左子节点时，将栈顶元素弹出，并将元素的值放入结果数组中。然后处理元素的右子节点。

所以，栈中元素的左子节点永远在当前元素的上面。按照栈的规则，先弹出左子节点，再弹出当前节点，最后弹出右子节点。这样就达到了中序遍历的目的。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    let result = [];
    let stack = [];
    let node = root;
    while(stack.length || node) {
        if (node) {
            stack.push(node);
            node = node.left;
            continue;
        }
        node = stack.pop();
        result.push(node.val);
        node = node.right;
    }
    return result;
};

总结

这里分别采用了递归和迭代的方式来实现中序遍历。递归的思路很好理解，这里需要重点掌握迭代的方式。而递归的方法使用了栈来存储元素，核心思路是只要当前节点有左子节点就放入栈中，没有便弹出进行处理当前节点，然后处理右子节点，继续判断右子节点是否有它自己的左子节点。使用栈刚好让左子节点位于当前节点的上面，这样处理的顺序就刚好是左中右。

145. 二叉树的后序遍历

力扣题目链接 (opens new window)

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

示例1：

输入：root = [1,null,2,3]
输出：[3,2,1]

提示：

• 树中节点的数目在范围 [0, 100] 内
• 100 <= Node.val <= 100

**进阶：**递归算法很简单，你可以通过迭代算法完成吗？

思路：

与二叉树的前序遍历和中序遍历一样，我们先写递归版本，再看迭代版本。

递归

写过前序和中序遍历的递归，想必后序遍历也不在话下。需要注意将节点的值放入结果数组的顺序。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function(root) {
    let result = [];
    const postOrder = (root) => {
        if (!root) return;
        postOrder(root.left);
        postOrder(root.right);
        result.push(root.val);
    }
    postOrder(root);
    return result;
};

迭代

后序遍历的迭代版本跟前序遍历的很相似。不同之处在于如何放入栈以及放入结果数组中。

后序遍历的顺序是左右根，而前序遍历的顺序是根左右。我们这里使用unshift就可以实现前序遍历的逆序，也就是右左根。而实现最终左右根的效果，只需要将入栈顺序调整一下即可。先将左子节点入栈，再将右子节点入栈。然后出栈的时候，就是根节点、右子节点、左子节点的顺序。依次从头部放入结果数组中。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function(root) {
    let result = [];
    let stack = [];
    if (root) stack.push(root);
    while(stack.length) {
        const root = stack.pop();
        result.unshift(root.val);
        if (root.left) stack.push(root.left);
        if (root.right) stack.push(root.right);
    }
    return result;
};

总结

我们通过连续三天的题解来分析了二叉树的前中后序遍历。同时介绍了递归和迭代两种方式。通过比较可以发现，递归的思路都是相同的，唯一不同之处在于将节点的值放入结果数组的时机。

而迭代都采用了栈的方式来实现，其中前序和后序遍历的迭代方式是类似的，不同之处在于放入结果数组的方式，以及左右子节点放入栈中的顺序。中序遍历比较特殊，需要不断寻找左子节点，直到找不到为止。只有这样才能达到左中右的顺序。