《剑指 Offer （第 2 版）》栈部分 JavaScript 题解
《剑指 Offer（第 2 版）》通行全球的程序员经典面试秘籍。剖析典型的编程面试题，系统整理基础知识、代码质量、解题思路、优化效率和综合能力这 5 个面试要点。
最近，把「栈」部分的题刷完了。本文来分享下这些题的解法
06. 从尾到头打印链表
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
「示例 1：」
输入：head = [1,3,2] 输出：[2,3,1]
「限制：」
0 <= 链表长度 <= 10000
题目地址：https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/
「运用栈的解题思路」
遍历链表，遍历的顺序是从头到尾，可输出的顺序却是从尾到头；也就是说第一个遍历到的节点最后一个输出，而最后一个遍历到的节点第一个输出。这个就是典型的后进先出，我们可以用栈来实现这种顺序，每经过一个节点的时候，把该节点放到一个栈中，当遍历完整个链表后，再从栈顶开始依次输出节点的值
/** * @param {ListNode} head * @return {number[]} */ var reversePrint = function(head) { let nodes = []; while (head != null) { nodes.push(head.val); head = head.next; } // 可以不用下面这一整段，直接 return nodes.reverse(); let result = []; let temp = nodes.pop(); while (temp != null) { result.push(temp); temp = nodes.pop(); } return result; };
09. 用两个栈实现队列
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
「示例 1：」
输入： ["CQueue","appendTail","deleteHead","deleteHead"] [[],[3],[],[]] 输出：[null,null,3,-1]
「示例 2：」
输入： ["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"] [[],[],[5],[2],[],[]] 输出：[null,-1,null,null,5,2]
「提示：」
1 <= values <= 10000最多会对 appendTail、deleteHead 进行 10000 次调用
题目地址：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/
「解题思路」
首先我们知道，队列是先入先出，栈是后入先出，所以知道了这两个东西的特性，我们很容易就能根据题意使用两个栈来模拟队列。
首先，两个栈分工不同，一个为入队栈，一个为出队栈，各自负责入队和出队。
入队操作，直接压入入队栈即可，出队操作需要优先检查出队栈是否有数据，若无，需要从入队栈倒入后再操作。
var CQueue = function() { this.enterStack = []; this.leaveStack = []; }; /** * @param {number} value * @return {void} */ CQueue.prototype.appendTail = function(value) { this.enterStack.push(value); }; /** * @return {number} */ CQueue.prototype.deleteHead = function() { if (this.leaveStack.length) { return this.leaveStack.pop(); } else { while(this.enterStack.length) { this.leaveStack.push(this.enterStack.pop()); } return this.leaveStack.length ? this.leaveStack.pop() : -1; } }; /** * Your CQueue object will be instantiated and called as such: * var obj = new CQueue() * obj.appendTail(value) * var param_2 = obj.deleteHead() */
30. 包含min函数的栈
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
「示例:」
MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.min(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.min(); --> 返回 -2.
「提示：」
- 各函数的调用总次数不超过 20000 次
题目地址：https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/
「解题思路」根据题意，我们需要在常量级的时间内找到最小值！
这说明，我们绝不能在需要最小值的时候，再做排序，查找等操作来获取！
所以，我们可以创建两个栈，一个栈是主栈 stack，另一个是辅助栈 minStack，用于存放对应主栈不同时期的最小值。
/** * initialize your data structure here. */ var MinStack = function() { this.stack = []; this.minStack = [Infinity]; }; /** * @param {number} x * @return {void} */ MinStack.prototype.push = function(x) { this.stack.push(x); this.minStack.push(Math.min(this.minStack[this.minStack.length - 1], x)); }; /** * @return {void} */ MinStack.prototype.pop = function() { this.stack.pop(); this.minStack.pop(); }; /** * @return {number} */ MinStack.prototype.top = function() { return this.stack[this.stack.length - 1]; }; /** * @return {number} */ MinStack.prototype.min = function() { return this.minStack[this.minStack.length - 1]; }; /** * Your MinStack object will be instantiated and called as such: * var obj = new MinStack() * obj.push(x) * obj.pop() * var param_3 = obj.top() * var param_4 = obj.min() */
31. 栈的压入、弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
「示例 1：」
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1] 输出：true 解释：我们可以按以下顺序执行： push(1), push(2), push(3), push(4), pop() -> 4, push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
「示例 2：」
输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2] 输出：false 解释：1 不能在 2 之前弹出。
「提示：」
0 <= pushed.length == popped.length <= 10000 <= pushed[i], popped[i] < 1000pushed是popped的排列。
题目地址：https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/
「解题思路」
- 按照入栈序列的顺序压栈
- 每次压栈之后，循环判断 “栈顶元素 = 弹出序列的当前元素” 是否成立，将符合弹出序列顺序的栈顶元素全部弹出
- 最后如果栈为空则满足条件，否则不满足
/** * @param {number[]} pushed * @param {number[]} popped * @return {boolean} */ var validateStackSequences = function(pushed, popped) { let index = 0; const stack = []; for(const value of pushed) { stack.push(value); while(stack.length && stack[stack.length - 1] === popped[index]) { stack.pop(); index ++; } } return stack.length === 0; };
33. 二叉搜索树的后序遍历序列
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树：
5 / \ 2 6 / \ 1 3
「示例 1：」
输入: [1,6,3,2,5] 输出: false
「示例 2：」
输入: [1,3,2,6,5] 输出: true
「提示：」
数组长度 <= 1000
题目地址：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/
「解题思路」
- 二叉搜索树一个特性就是：左子树比根节点小，右子树比根节点大
- 只要找到左右子树的分界点，然后递归的去判定就好了
- 中途有任何不满足的就直接返回
false就ok
/** * @param {number[]} postorder * @return {boolean} */ var verifyPostorder = function(postorder) { function verify(start, end) { if (start > end) return true; let mid1 = start; while(postorder[mid1] < postorder[end]) { mid1 ++; } let mid2 = end - 1; while(postorder[mid2] > postorder[end]) { mid2 --; } return mid1 - 1 === mid2 && verify(start, mid1 - 1) && verify(mid1, end - 1); } return verify(0, postorder.length - 1); };
36. 二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
为了让您更好地理解问题，以下面的二叉搜索树为例：
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
题目地址：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
「解题思路」
二叉搜索树的中序遍历便是升序的，自然而然的，我们便先中序遍历将节点保存下来，然后将他们相连成循环双向链表。
/** * // Definition for a Node. * function Node(val,left,right) { * this.val = val; * this.left = left; * this.right = right; * }; */ /** * @param {Node} root * @return {Node} */ var treeToDoublyList = function(root) { if (root === null) return null; const stk = [], nodeList = []; let node = root; while(stk.length || node) { while(node) { stk.push(node); node = node.left; } node = stk.pop(); nodeList.push(node); node = node.right; } nodeList.push(nodeList[0]); for(let i = 1; i < nodeList.length - 1; i++) { nodeList[i].right = nodeList[i + 1]; nodeList[i].left = nodeList[i - 1]; } nodeList[0].right = nodeList[1]; nodeList[0].left = nodeList[nodeList.length - 2]; return nodeList[0]; };
