栈
# lc20. 求有效的括号 简单hot
题目描述
给定一个只包括'('，')'，'{'，'}'，'['，']'的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。
示例：
输入：s = "()"
输出：true
输入：s = "()[]{}"
输出：true
输入：s = "([)]"
输出：false
输入：s = "{[]}"
输出：true
2
3
4
5
6
7
8
9
10
11
思路：
借助了map数据结构，同时用了栈的思想，新增一个stackArr的数组，通过循环遍历输入字符串判断：
如果输入字符串在Map中存在（正括号存在即合理），继续循环
如果不存在，再获取缓存中最后一项的值进行配对～配对成功即合理、移除当前缓存
继续循环直到遍历完成
遍历完成后如果缓存中仍有数据、说明有正括号未匹配结果，则
return false，反之return true
var isValid = function(s) {
const stackArr = []
const map = new Map()
map.set('(', ')')
map.set('{', '}')
map.set('[', ']')
for(let i = 0; i < s.length; i++) {
if(map.has(s[i])) stackArr.push(s[i])
else {
if(stackArr.length === 0) return false
if (map.get(stackArr[stackArr.length - 1]) === s[i]) stackArr.pop()
else return false
}
}
if(stackArr.length) return false
return true
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
时间复杂度: O(n)
空间复杂度: O(n)
# lc32. 最长有效括号困难hot
题目描述
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
2
3
示例 2：
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
2
3
示例 3：
输入：s = ""
输出：0
2
思路
对于遇到的每个 ( ，我们将它的下标放入栈中
对于遇到的每个 ) ，我们先弹出栈顶元素表示匹配了当前右括号：
- 如果栈为空，说明当前的右括号为没有被匹配的右括号，我们将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」
- 如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」
- 我们从前往后遍历字符串并更新答案即可。
需要注意的是，如果一开始栈为空，第一个字符为左括号的时候我们会将其放入栈中，这样就不满足提及的「最后一个没有被匹配的右括号的下标」，为了保持统一，我们在一开始的时候往栈中放入一个值为 −1 的元素。
var longestValidParentheses = function(s) {
let stack = [-1], ans = 0;
for (let i = 0; i < s.length; i++) {
if (s[i] === '(') {
stack.push(i)
} else {
stack.pop();
if (stack.length === 0) {
stack.push(i)
} else {
ans = Math.max(ans, i - stack[stack.length - 1])
}
}
}
return ans;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
时间复杂度: O(n)
空间复杂度: O(n)
前后同时遍历
用两个计数器 left 和 right 。
从左到右遍历字符串，遇到(，我们增加left 计数器，对于遇到的每个 ) ，我们增加 right 计数器。每当 left 计数器与 right 计数器相等时，我们计算当前有效字符串的长度，并且记录目前为止找到的最长子字符串。当 right 计数器比 left 计数器大时，我们将 left 和 right 计数器同时变回 0。
这样的做法贪心地考虑了以当前字符下标结尾的有效括号长度，每次当右括号数量多于左括号数量的时候之前的字符我们都扔掉不再考虑，重新从下一个字符开始计算，但这样会漏掉一种情况，就是遍历的时候左括号的数量始终大于右括号的数量，即 (() ，这种时候最长有效括号是求不出来的。
解决的方法也很简单，我们只需要从右往左遍历用类似的方法计算即可，只是这个时候判断条件反了过来：
当 left 计数器比 right 计数器大时，我们将 left 和 right 计数器同时变回 0
当 left 计数器与 right 计数器相等时，我们计算当前有效字符串的长度，并且记录目前为止找到的最长子字符串
var longestValidParentheses = function(s) {
let left = 0, right = 0, maxlength = 0;
for (let i = 0; i < s.length; i++) {
if (s[i] === '(') {
left++;
} else {
right++;
}
if (left === right) {
maxlength = Math.max(maxlength, 2 * right);
} else if (right > left) {
left = right = 0;
}
}
left = right = 0;
for (let i = s.length - 1; i >= 0; i--) {
if (s[i] === '(') {
left++;
} else {
right++;
}
if (left === right) {
maxlength = Math.max(maxlength, 2 * left);
} else if (left > right) {
left = right = 0;
}
}
return maxlength;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
时间复杂度: O(n)
空间复杂度: O(1)
# lc. 1047删除字符串中的相邻重复项简单
题目描述
给出由小写字母组成的字符串S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：
输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同
这是此时唯一可以执行删除操作的重复项。
之后我们得到字符串 "aaca"
其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
2
3
4
5
6
7
思路：
我们都刷了这么多题了，第一反应肯定是用栈弹出的形式来匹配是否相同的
那么我们可以维护一个栈数组
如果栈顶元素与将要入栈的元素相同的话
那么栈顶元素出栈
很简单是不是
时间复杂度O(n)
空间复杂度O(n)
var removeDuplicates = function(s) {
const stack = []
// 发现新大陆 ！字符串也可以用for .. of..
for(c of s) {
let temp = stack.pop()
if(c !== temp) {
stack.push(temp)
stack.push(c)
}
}
return stack.join('')
};
2
3
4
5
6
7
8
9
10
11
12
这里奇奇怪怪的，时间复杂度为O(n) 但是跑了几次都只击败了10%左右的用户，莫非还有O(1)的空间复杂度，暂时没找到，先mark一下
# lc1209. 删除字符串中的相邻重复项中等
题目描述：
给你一个字符串 s，「k倍重复项删除操作」将会从 s 中选择 k 个相邻且相等的字母，并删除它们，使被删去的字符串的左侧和右侧连在一起。
你需要对 s 重复进行无限次这样的删除操作，直到无法继续为止。
在执行完所有删除操作后，返回最终得到的字符串。
本题答案保证唯一。
示例 1：
输入：s = "abcd", k = 2
输出："abcd"
解释：没有要删除的内容。
2
3
示例 2：
输入：s = "deeedbbcccbdaa", k = 3
输出："aa"
解释：
先删除 "eee" 和 "ccc"，得到 "ddbbbdaa"
再删除 "bbb"，得到 "dddaa"
最后删除 "ddd"，得到 "aa"
2
3
4
5
6
示例 3：
输入：s = "pbbcggttciiippooaais", k = 2
输出："ps"
2
法一：把进栈的字母相同 改为 合并为同一个元素
- 每次入栈元素和栈顶元素匹配
- 注意栈顶元素可能不只是一个字母
如果栈顶元素的第一位和入栈元素不相同
- 准备入栈的元素执行入栈操作
如果栈顶元素的第一位和入栈元素相同
- 判断一下栈顶元素长度是不是等于
k - 1(因为等于k - 1的话加上这个入栈元素就是k位，那么就可以出栈了) - 等于栈顶元素就出栈
- 不等于就把栈顶元素和入栈元素拼接起来 然后重新替换原来的栈顶元素 执行入栈
- 判断一下栈顶元素长度是不是等于
时间复杂度O(n)
空间复杂度O(n)
var removeDuplicates = function(s, k) {
const stack = []
for(let c of s) {
const prev = stack.pop()
if(!prev || c !== prev[0]) {
stack.push(prev)
stack.push(c)
} else if(prev.length < k - 1) {
stack.push(prev + c)
}
}
return stack.join('')
};
2
3
4
5
6
7
8
9
10
11
12
13
法二 维护一个计算次数的栈和储存元素的栈
执行一遍循环
如果入栈元素和栈顶元素相同
- 数字栈的栈顶元素加一
- 如果累积到
k了 储存元素的栈执行k次出栈
如果入栈元素和栈顶元素不同
- 那么入栈元素入储存元素的栈 数字栈推入一个为
1的元素
- 那么入栈元素入储存元素的栈 数字栈推入一个为
时间复杂度O(n)
空间复杂度O(n)
var removeDuplicates = function (s, k) {
let stack = [] //字母栈
let countStack = [] //数字栈
let i = 0
while(i < s.length){
if(stack[stack.length - 1] == s[i]){
stack.push(s[i])
countStack[countStack.length-1] += 1
if(countStack[countStack.length-1] == k){
for(let j = 0; j < k; j++){
//字母栈出栈
stack.pop()
}
countStack.pop() //数字栈出栈
}
}else{
stack.push(s[i])
countStack.push(1)
}
i++
}
return stack.join('')
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
这里很奇怪的是两种方法都是时间复杂度O(n) 空间复杂度O(n) 但是执行用时却有很大的差别，有待考究
# lc150. 逆波兰表达式求值中等
题目描述
根据 逆波兰表示法 (opens new window)，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
注意 两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
2
3
示例 2：
输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
2
3
示例 3：
输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
2
3
4
5
6
7
8
9
10
var evalRPN = function(tokens) {
let methods = ['+', '-', '*', '/']
const stack = []
for(let item of tokens) {
if(!methods.includes(item)) stack.push(+item)
else {
let num2 = stack.pop()
let num1 = stack.pop()
switch(item) {
case '+':
stack.push(num1 + num2)
break
case '-':
stack.push(num1 - num2)
break
case '*':
stack.push(num1 * num2)
break
case '/':
stack.push(Math.trunc(num1 / num2))
break
}
}
}
return stack[0]
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# lc155. 最小栈简单
题目描述
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x)—— 将元素 x 推入栈中。pop()—— 删除栈顶的元素。top()—— 获取栈顶元素。getMin()—— 检索栈中的最小元素。
示例:
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var MinStack = function() {
this.stack = []
this.min = +Infinity
// 辅助栈
// this.min_stack = [Infinity]
};
/**
* @param {number} val
* @return {void}
*/
MinStack.prototype.push = function(val) {
this.stack.push(val)
this.min = Math.min(this.min, val)
// 辅助栈
// this.min_stack.push(Math.min(this.min_stack[this.min_stack.length - 1], val));
};
/**
* @return {void}
*/
MinStack.prototype.pop = function() {
this.stack.pop()
this.min = Math.min(...this.stack)
// 辅助栈
// this.min_stack.pop();
};
/**
* @return {number}
*/
MinStack.prototype.top = function() {
return this.stack[this.stack.length - 1]
}
/**
* @return {number}
*/
MinStack.prototype.getMin = function() {
return this.min
// 辅助栈
// return this.min_stack[this.min_stack.length - 1];
};
/**
* 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()
*/
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
# lc225. 用队列实现栈
题目描述
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x)将元素 x 压入栈顶。int pop()移除并返回栈顶元素。int top()返回栈顶元素。boolean empty()如果栈是空的，返回true；否则，返回false。
注意：
- 你只能使用队列的基本操作 —— 也就是
push to back、peek/pop from front、size和is empty这些操作。 - 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
示例：
输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]
解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False
2
3
4
5
6
7
8
9
10
11
12
13
思路
尽量不要出现pop()
/**
* Initialize your data structure here.
*/
var MyStack = function() {
this.queue1 = [];
this.queue2 = [];
};
//
//
/**
* Push element x onto stack.
* @param {number} x
* @return {void}
*/
MyStack.prototype.push = function(x) {
this.queue2.push(x);
while (this.queue1.length) this.queue2.push(this.queue1.shift());
[this.queue1, this.queue2] = [this.queue2, this.queue1];
};
/**
* Removes the element on top of the stack and returns that element.
* @return {number}
*/
MyStack.prototype.pop = function() {
return this.queue1.shift();
};
/**
* Get the top element.
* @return {number}
*/
MyStack.prototype.top = function() {
return this.queue1[0];
};
/**
* Returns whether the stack is empty.
* @return {boolean}
*/
MyStack.prototype.empty = function() {
return !this.queue1.length;
};
/**
* Your MyStack object will be instantiated and called as such:
* var obj = new MyStack()
* obj.push(x)
* var param_2 = obj.pop()
* var param_3 = obj.top()
* var param_4 = obj.empty()
*/
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
# 单调栈
# lc739. 每日温度中等hot
题目描述
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指在第 i 天之后，才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。
示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
2
示例 2:
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]
2
示例 3:
输入: temperatures = [30,60,90]
输出: [1,1,0]
2
思路
维护一个单调递增栈，栈内存储气温数组
T的index查看当前元素是否大于栈顶元素所对应的
T的值，也就是T[stack[stack.length - 1]]如果大于，那说明找到需要等待的天数。如果不大于那说明还没到找到比这天高的温度。同时继续维护这个单调栈
如果大于，需要等待的天数就是当前数组
T的下标减去单调栈顶对应的下标循环完毕，还没有找到需要等待的天数，为
0
var dailyTemperatures = function(temperatures) {
const len = temperatures.length
const res = new Array(len).fill(0)
const stack = []
for(let i = 0; i < len; i++) {
while(stack.length && temperatures[stack[stack.length - 1]] < temperatures[i]) {
let index = stack.pop()
res[index] = i - index
}
stack.push(i)
}
return res
};
2
3
4
5
6
7
8
9
10
11
12
13
时间复杂度：O(n)，其中 n 是温度列表的长度。正向遍历温度列表一遍，对于温度列表中的每个下标，最多有一次进栈和出栈的操作。
空间复杂度：O(n)，其中 n 是温度列表的长度。需要维护一个单调栈存储温度列表中的下标。
# lc402. 移除掉k位数字中等
题目描述
给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。
示例 1 ：
输入：num = "1432219", k = 3
输出："1219"
解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。
2
3
4
5
示例 2 ：
输入：num = "10200", k = 1
输出："200"
解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
2
3
4
5
示例 3 ：
输入：num = "10", k = 2
输出："0"
解释：从原数字移除所有的数字，剩余为空就是 0 。
2
3
4
5
思路: 利用单调栈
/**
* @param {string} num
* @param {number} k
* @return {string}
*/
var removeKdigits = function(num, k) {
const stack = []
for(let i = 0; i < num.length; i++) {
while(k && num[i] < stack[stack.length - 1] && stack.length) {
stack.pop()
k--
}
stack.push(num[i])
}
// 一直进栈导致 k 还没变成 0 栈需要把最后几位出栈，凑齐删除k位
while(k--) {
stack.pop()
}
// 去除先导零
while(stack.length && stack[0] === '0') {
stack.shift()
}
const fi = stack.join('')
return fi ? fi : '0'
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# lc316. 去除重复字母中等
题目描述
给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
示例 1：
输入：s = "bcabc"
输出："abc"
示例 2：
输入：s = "cbacdcbc"
输出："acdb"
2
3
4
5
6
7
8
9
思路
这道题的关键在于他要求的字典序最小
让我们以 bcabc为栗子
首先遍历到
bc都是无重复的 入栈然后开始遍历
a， 首先a是比bc都小的其次 如果要以
a开头的话就得看看a后面还有没有c- 如果有的话 那么可以放心大胆让栈顶的元素 先出栈(之后有
c) - 如果没有的话栈顶元素不出栈
- 如果有的话 那么可以放心大胆让栈顶的元素 先出栈(之后有
/**
* @param {string} s
* @return {string}
*/
var removeDuplicateLetters = function(s) {
const stack = []
for(let i = 0; i < s.length; i++) {
if(stack.indexOf(s[i]) > -1) continue
while(stack.length && stack[stack.length - 1] > s[i] && s.indexOf(stack[stack.length - 1], i) > i) {
stack.pop()
}
stack.push(s[i])
}
return stack.join('')
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16