stack | 栈
有效的括号
限制的括号 []{}()
使用栈完美解决，当匹配的括号与栈顶元素相反，或者 ASCII的差值值 ) - ( 为 1, ] - [, } - { 的差值为 2.所以用栈可以简单实现
Q & A
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
var stack = []
for(const i of s) {
const it = stack.length && stack.slice(-1)[0] || 0
const ret = i.charCodeAt() - it.charCodeAt()
switch(ret){
case 1:
case 2:
stack.pop()
break
default:
stack.push(i)
break
}
}
return stack.length === 0 ? true : false
};
二叉树的生成
为了方便，此后的树的生成都用改方法
function TreeNode(val, left, right) {
this.val = val === undefined ? 0 : val;
this.left = left === undefined ? null : left;
this.right = right === undefined ? null : right;
}
// 层序生成
function createTree(arr, root, i = 0) {
if (i < arr.length && arr[i] !== null) {
let temp = new TreeNode(arr[i]);
root = temp;
// 左子树节点的下标总是 2*parent + 1, 右子树总是 2*parent + 2
root.left = createTree(arr, root.left, 2 * i + 1);
root.right = createTree(arr, root.right, 2 * i + 2);
}
return root;
}
二叉树的前序遍历
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
有两种方案简单的递归和优化递归
二叉树的前序遍历顺序为：中 -> 左 -> 右
简单版递归方案
简易版递归写法
var preorderTraversal = function(root) {
const ret = []
function dfs(node) {
if (node === null) return
ret.push(node.val)
dfs(node.left)
dfs(node.right)
}
dfs(root)
return ret
};
var root = createTree([1,2,3,4,5,6,7])
preorderTraversal(root) // 1,2,4,5,3,6,7
统一简版写法
使用 es6 的扩展运算符 reset
统一综合递归写法, 只需要交换 root.val 的位置即可
var preorderTraversal = function(root) {
return root
&& [ root.val, ...preorderTraversal(root.left), ...preorderTraversal(root.right)]
|| []
};
var root = createTree([1,2,3,4,5,6,7])
preorderTraversal(root) // 1,2,4,5,3,6,7
迭代实现递归栈写法
模拟递归的栈调度实现
var preorderTraversal = function(root) {
const ret = []
if (!root) return ret
const stack = [root]
while (stack.length) {
const current = stack.pop()
ret.push(current.val)
// 先处理左边的，所以右边的先入栈
current.right && stack.push(current.right)
current.left && stack.push(current.left)
}
return ret
};
var root = createTree([1,2,3,4,5,6,7])
preorderTraversal(root) // 1,2,4,5,3,6,7
// 记忆版
var preorderTraversal = function(root) {
const ret = []
if (!root) return ret
const stack = []
while (root || stack.length) {
// 找到最左侧叶子节点
while (root) {
ret.push(root.val)
stack.push(root);
root = root.left;
}
// 节点的左子节点为null，跳出while循环,继续遍历右子节点
root = stack.pop().right;
}
return ret
};
// 双色标记法
var preorderTraversal = function(root) {
const COLOR = {
WHITE: 0, // 没有访问过
GRAY: 1 // 已经访问过
}
const ret = []
const stack = [[COLOR.WHITE, root]]
while(stack.length) {
const [color, node] = stack.pop();
if (!node) continue;
if (color === COLOR.WHITE) {
stack.push([COLOR.WHITE, node.right])
stack.push([COLOR.WHITE, node.left])
// 改动这里的推入顺序
stack.push([COLOR.GRAY, node])
} else {
ret.push(node.val)
}
}
return ret
};
二叉树的中序遍历
给定一个二叉树的根节点 root ，返回它的 中序 遍历。
二叉树的中序遍历顺序为：左 -> 中 -> 右
简单版递归方案
var inorderTraversal = function(root) {
const ret = []
function dfs(node) {
if (!node) return
dfs(node.left)
ret.push(node.val) //只是这里改变了位置
dfs(node.right)
}
dfs(root)
return ret
};
var root = createTree([1,2,3,4,5,6,7])
inorderTraversal(root) // [4,2,5,1,6,3,7]
统一简版写法
使用 es6 的扩展运算符 reset
统一综合递归写法, 只需要交换 root.val 的位置即可
var inorderTraversal = function(root) {
return root
&& [...inorderTraversal(root.left), root.val, ...inorderTraversal(root.right)]
|| []
};
var root = createTree([1,2,3,4,5,6,7])
inorderTraversal(root) // [4,2,5,1,6,3,7]
迭代实现递归写法
var inorderTraversal = function(root) {
const ret = []
if(!root) return ret
const stack = []
// 如果栈未清空就一直执行
while(root || stack.length) {
// 先处理当前左边的子节点, 直到 null 返回
while(root) {
stack.push(root)
// 依次找到最底层的左侧子节点
root = root.left
}
// 先弹出最上边左边叶子节点
root = stack.pop()
ret.push(root.val)
root = root.right
}
return ret
};
var root = createTree([1,2,3,4,5,6,7])
inorderTraversal(root) // [4,2,5,1,6,3,7]
// 记忆版
var inorderTraversal = function(root) {
const ret = []
if(!root) return ret
const stack = []
while(root || stack.length) {
// 找到最左侧叶子节点
while(root) {
stack.push(root)
root = root.left
}
// 取出当前节点
let current = stack.pop()
ret.push(current.val)
root = current.right
}
return ret
};
// 双色标记法
var inorderTraversal = function(root) {
const COLOR = {
WHITE: 0, // 没有访问过
GRAY: 1 // 已经访问过
}
const ret = []
const stack = [[COLOR.WHITE, root]]
while(stack.length) {
const [color, node] = stack.pop();
if (!node) continue;
if (color === COLOR.WHITE) {
stack.push([COLOR.WHITE, node.right])
// 改动这里的推入顺序
stack.push([COLOR.GRAY, node])
stack.push([COLOR.WHITE, node.left])
} else {
ret.push(node.val)
}
}
return ret
};
二叉树的后序遍历
给定一个二叉树，返回它的 后序 遍历。
简单版递归方案
var postorderTraversal = function(root) {
const ret = []
function dfs(node) {
if (!node) return
dfs(node.left)
dfs(node.right)
ret.push(node.val) // ==> 注意，三种方式，只是这里改变了位置
}
dfs(root)
return ret
};
var root = createTree([1,2,3,4,5,6,7])
postorderTraversal(root) // [4,5,2,6,7,3,1]
统一简版写法
使用 es6 的扩展运算符 reset
统一综合递归写法, 只需要交换 root.val 的位置即可
var postorderTraversal = function(root) {
return root
&& [...postorderTraversal(root.left), ...postorderTraversal(root.right), root.val]
|| []
};
var root = createTree([1,2,3,4,5,6,7])
postorderTraversal(root) // [4,5,2,6,7,3,1]
迭代实现递归写法
var postorderTraversal = function(root) {
const ret = []
if(!root) return ret
const stack = [root]
while(stack.length) {
const current = stack.pop()
if(current == null) {
ret.push(stack.pop().val);
}else {
stack.push(current)
// 在这里切分支
stack.push(null)
current.right && stack.push(current.right);
current.left && stack.push(current.left);
}
}
return ret
};
var root = createTree([1,2,3,4,5,6,7])
postorderTraversal(root) // [4,5,2,6,7,3,1]
// 记忆版
var postorderTraversal = function(root) {
const ret = []
if(!root) return ret
const stack = []
let visited = null
while(root || stack.length) {
// 一直查找到最左边的叶子节点
while(root) {
stack.push(root)
root = root.left
}
const current = stack.pop()
// 当当前节节点的右叶子节点为空 | 被访问过
if (current.right === null || current.right === visited) {
ret.push(current.val)
visited = current
} else {
stack.push(current)
root = current.right
}
}
return ret
}
// 双色标记法
var postorderTraversal = function(root) {
const COLOR = {
WHITE: 0, // 没有访问过
GRAY: 1 // 已经访问过
}
const ret = []
const stack = [[COLOR.WHITE, root]]
while(stack.length) {
const [color, node] = stack.pop();
if (!node) continue;
if (color === COLOR.WHITE) {
// 改动这里的推入顺序
stack.push([COLOR.GRAY, node])
stack.push([COLOR.WHITE, node.right])
stack.push([COLOR.WHITE, node.left])
} else {
ret.push(node.val)
}
}
return ret
};
用两个栈实现队列
LeetCode 剑指 Offer 09. 用两个栈实现队列
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
思路
- 初始化两个栈，一个栈用来只进栈(in)，一直只负责出栈(out)
- 当 in 栈中存在元素，要删除的时候，就依次出栈，out 在依次存入入栈的元素，这样栈顶就是 队头的元素 然后进行 out 栈的出栈操作，就是删除头
- 当后续进行再次删除的时候，因为我们之前存在的队列的元素如果在 out 中还存在，就弹出
var CQueue = function() {
// 两个栈
// 进栈
this.inStack = []
// 出栈
this.outStack = []
};
/**
* @param {number} value
* @return {void}
*/
CQueue.prototype.appendTail = function(value) {
this.inStack.push(value)
};
/**
* @return {number}
*/
CQueue.prototype.deleteHead = function() {
// 如果出栈中存在元素，表示还存在队列的头部元素，直接取出
if (this.outStack.length) return this.outStack.pop()
// 不存在直接重新入栈
while (this.inStack.length) this.outStack.push(this.inStack.pop())
// 如果入栈之后，存在元素就返回，不存在返回-1
return this.outStack.length && this.outStack.pop() || -1
};
设计一个支持增量操作的栈
LeetCode 剑指 Offer 10. 设计一个支持增量操作的栈
请你设计一个支持下述操作的栈。
实现自定义栈类 CustomStack ：
CustomStack(int maxSize)：用 maxSize 初始化对象，maxSize 是栈中最多能容纳的元素数量，栈在增长到 maxSize 之后则不支持 push 操作。
void push(int x)：如果栈还未增长到 maxSize ，就将 x 添加到栈顶。
int pop()：弹出栈顶元素，并返回栈顶的值，或栈为空时返回 -1 。
void inc(int k, int val)：栈底的 k 个元素的值都增加 val 。如果栈中元素总数小于 k ，则栈中的所有元素都增加 val 。
示例：
输入：
["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"]
[[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]
输出：
[null,null,null,2,null,null,null,null,null,103,202,201,-1]
解释：
CustomStack customStack = new CustomStack(3); // 栈是空的 []
customStack.push(1); // 栈变为 [1]
customStack.push(2); // 栈变为 [1, 2]
customStack.pop(); // 返回 2 --> 返回栈顶值 2，栈变为 [1]
customStack.push(2); // 栈变为 [1, 2]
customStack.push(3); // 栈变为 [1, 2, 3]
customStack.push(4); // 栈仍然是 [1, 2, 3]，不能添加其他元素使栈大小变为 4
customStack.increment(5, 100); // 栈变为 [101, 102, 103]
customStack.increment(2, 100); // 栈变为 [201, 202, 103]
customStack.pop(); // 返回 103 --> 返回栈顶值 103，栈变为 [201, 202]
customStack.pop(); // 返回 202 --> 返回栈顶值 202，栈变为 [201]
customStack.pop(); // 返回 201 --> 返回栈顶值 201，栈变为 []
customStack.pop(); // 返回 -1 --> 栈为空，返回 -1
提示：
1 <= maxSize <= 1000
1 <= x <= 1000
1 <= k <= 1000
0 <= val <= 100
每种方法 increment，push 以及 pop 分别最多调用 1000 次
思路
使用数组模拟
- push: 当数组长度 >= maxSize 时不push否则添加
- pop: 只需要关心当前数组长度即可
- increment: 只需要关心当前数组长度和k的关系
代码
var CustomStack = function(maxSize) {
this.stack = []
this.maxSize = maxSize || 0
};
CustomStack.prototype.push = function(x) {
if (this.stack.length >= this.maxSize) return false
this.stack.push(x)
};
CustomStack.prototype.pop = function() {
return this.stack.length
&& this.stack.pop()
|| -1
};
CustomStack.prototype.increment = function(k, val) {
const length = Math.min(k, this.stack.length)
for (let i = 0; i < length; i++) this.stack[i] += val
}
复杂度分析
时间复杂度: [push, pop] 为O(1) increment 为 O(n)
空间复杂度: O(n)
用栈实现队列
info
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明
你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
进阶
你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。
思路
使用两个栈，in 和 out
in用来输入，push 或者判空out用来输出，只有当 out 为空的时候，才需要转置 in 栈，因为 out 里存的一直都是队列的头部
代码
var MyQueue = function() {
this.in = []
this.out = []
};
MyQueue.prototype.push = function(x) {
this.in.push(x)
};
MyQueue.prototype.pop = function() {
if (this.out.length) return this.out.pop()
else this.transpose()
return this.out.pop()
};
MyQueue.prototype.transpose = function() {
while (this.in.length) this.out.push(this.in.pop())
}
MyQueue.prototype.peek = function() {
if (this.out.length) return this.out[this.out.length - 1]
else this.transpose()
return this.out[this.out.length - 1]
};
MyQueue.prototype.empty = function() {
if (this.in.length | this.out.length) return false
else return true
};
复杂度分析
- 时间复杂度: O(1)
- 空间复杂度: O(n)
最多能完成排序的块 II
info
这个问题和“最多能完成排序的块”相似，但给定数组中的元素可以重复，输入数组最大长度为2000，其中的元素最大为10**8。
arr是一个可能包含重复元素的整数数组，我们将这个数组分割成几个“块”，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。
我们最多能将数组分成多少块？
示例 1:
输入: arr = [5,4,3,2,1]
输出: 1
解释:
将数组分成2块或者更多块，都无法得到所需的结果。
例如，分成 [5, 4], [3, 2, 1] 的结果是 [4, 5, 1, 2, 3]，这不是有序的数组。
示例 2:
输入: arr = [2,1,3,4,4]
输出: 4
解释:
我们可以把它分成两块，例如 [2, 1], [3, 4, 4]。
然而，分成 [2, 1], [3], [4], [4] 可以得到最多的块数。
注意:
arr的长度在[1, 2000]之间。
arr[i]的大小在[0, 10**8]之间。
思路
单调栈
- 栈顶记录最大值
- 遍历每个元素
- 如果当前元素大于等于栈顶元素，入栈
- 如果小于当前栈顶元素，循环出栈，直到当前元素大于等于栈顶元素
- 重新更新 max
代码
var maxChunksToSorted = function (arr) {
const stack = []
const peek = array => array.length >= 1 ? array[array.length - 1] : 0
for (const n of arr) {
const max = peek(stack)
if (stack.length && n < max) {
// 循环出栈
while (stack.length && n < peek(stack)) stack.pop()
// 更新 max
stack.push(max)
} else stack.push(n)
}
// 返回高度
return stack.length
};
复杂度分析
时间复杂度: O(n)
空间复杂度: O(n)