本节内容
- 20. 有效的括号
- 1047. 删除字符串中的所有相邻重复项
- 150. 逆波兰表达式求值
20. 有效的括号※
建议：讲完了栈实现队列，队列实现栈，接下来就是栈的经典应用了。
大家先自己思考一下 有哪些不匹配的场景，在看视频 我讲的都有哪些场景，落实到代码其实就容易很多了。
题目链接： https://leetcode.cn/problems/valid-parentheses/
文章讲解： https://programmercarl.com/0020.%E6%9C%89%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7.html
https://www.yuanql.top/2023/07/04/02_leetcode/20.%20%E6%9C%89%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7/
题目分析
将数据一个放入到栈中，每次和栈顶的数据进行比对，比对成功就弹出。
方案一
1
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
| class Solution {
public boolean isValid(String s) {
Deque<Character> deque = new LinkedList();
for (Character ch :
s.toCharArray()) {
switch (ch) {
case '{':
deque.offerLast(ch);
break;
case '[':
deque.offerLast(ch);
break;
case '(':
deque.offerLast(ch);
break;
case '}':
if (!deque.isEmpty() && deque.peekLast() == '{') {
deque.pollLast();
} else {
deque.offerLast(ch);
}
break;
case ']':
if (!deque.isEmpty() && deque.peekLast() == '[') {
deque.pollLast();
} else {
deque.offerLast(ch);
}
break;
case ')':
if (!deque.isEmpty() && deque.peekLast() == '(') {
deque.pollLast();
} else {
deque.offerLast(ch);
}
break;
}
}
return deque.isEmpty();
}
}
|
结果
解答成功:
执行耗时:1 ms,击败了97.69% 的Java用户
内存消耗:39.5 MB,击败了69.98% 的Java用户
分析
时间复杂度：
O( n )
空间复杂度：
O( n )
代码随想录
https://programmercarl.com/0020.%E6%9C%89%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7.html#%E8%BF%9B%E5%85%A5%E6%AD%A3%E9%A2%98
由于栈结构的特殊性，非常适合做对称匹配类的题目。
首先要弄清楚，字符串里的括号不匹配有几种情况。
一些同学，在面试中看到这种题目上来就开始写代码，然后就越写越乱。
建议在写代码之前要分析好有哪几种不匹配的情况，如果不在动手之前分析好，写出的代码也会有很多问题。
先来分析一下 这里有三种不匹配的情况，
第一种情况，字符串里左方向的括号多余了 ，所以不匹配。
第二种情况，括号没有多余，但是 括号的类型没有匹配上
第三种情况，字符串里右方向的括号多余了，所以不匹配。
我们的代码只要覆盖了这三种不匹配的情况，就不会出问题，可以看出 动手之前分析好题目的重要性。
动画如下：
第一种情况：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false
第二种情况：遍历字符串匹配的过程中，发现栈里没有要匹配的字符。所以return false
第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false
那么什么时候说明左括号和右括号全都匹配了呢，就是字符串遍历完之后，栈是空的，就说明全都匹配了。
分析完之后，代码其实就比较好写了，
但还有一些技巧，在匹配左括号的时候，右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了，比左括号先入栈代码实现要简单的多了！
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public boolean isValid(String s) {
Deque<Character> deque = new LinkedList<>();
char ch;
for (int i = 0; i < s.length(); i++) {
ch = s.charAt(i);
if (ch == '(') {
deque.push(')');
}else if (ch == '{') {
deque.push('}');
}else if (ch == '[') {
deque.push(']');
} else if (deque.isEmpty() || deque.peek() != ch) {
return false;
}else {
deque.pop();
}
}
return deque.isEmpty();
}
}
|
1047. 删除字符串中的所有相邻重复项※
建议：栈的经典应用。
要知道栈为什么适合做这种类似于爱消除的操作，因为栈帮助我们记录了 遍历数组当前元素时候，前一个元素是什么。
题目链接： https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/
文章讲解： https://programmercarl.com/1047.%E5%88%A0%E9%99%A4%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%AD%E7%9A%84%E6%89%80%E6%9C%89%E7%9B%B8%E9%82%BB%E9%87%8D%E5%A4%8D%E9%A1%B9.html
https://www.yuanql.top/2023/07/05/02_leetcode/1047.%20%E5%88%A0%E9%99%A4%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%AD%E7%9A%84%E6%89%80%E6%9C%89%E7%9B%B8%E9%82%BB%E9%87%8D%E5%A4%8D%E9%A1%B9/
题目分析
方案一
将不匹配的放到双端队列中，匹配后弹出队列（使用栈的思想）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public String removeDuplicates(String s) {
Deque<Character> deque = new LinkedList<>();
for (Character ch :
s.toCharArray()) {
if (!deque.isEmpty() && deque.peek() == ch) {
deque.pop();
} else {
deque.push(ch);
}
}
StringBuilder result = new StringBuilder();
while (!deque.isEmpty()) {
result.append(deque.pollLast());
}
return result.toString();
}
}
|
结果
解答成功:
执行耗时:18 ms,击败了79.82% 的Java用户
内存消耗:43.4 MB,击败了40.30% 的Java用户
分析
时间复杂度：
O( n )
空间复杂度：
O( n )
代码随想录
https://programmercarl.com/1047.%E5%88%A0%E9%99%A4%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%AD%E7%9A%84%E6%89%80%E6%9C%89%E7%9B%B8%E9%82%BB%E9%87%8D%E5%A4%8D%E9%A1%B9.html
本题也是用栈来解决的经典题目。
那么栈里应该放的是什么元素呢？
我们在删除相邻重复项的时候，其实就是要知道当前遍历的这个元素，我们在前一位是不是遍历过一样数值的元素，那么如何记录前面遍历过的元素呢？
所以就是用栈来存放，那么栈的目的，就是存放遍历过的元素，当遍历当前的这个元素的时候，去栈里看一下我们是不是遍历过相同数值的相邻元素。
然后再去做对应的消除操作。 如动画所示：
从栈中弹出剩余元素，此时是字符串ac，因为从栈里弹出的元素是倒序的，所以再对字符串进行反转一下，就得到了最终的结果。
代码实现
使用 Deque 作为堆栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public String removeDuplicates(String S) {
ArrayDeque<Character> deque = new ArrayDeque<>();
char ch;
for (int i = 0; i < S.length(); i++) {
ch = S.charAt(i);
if (deque.isEmpty() || deque.peek() != ch) {
deque.push(ch);
} else {
deque.pop();
}
}
String str = "";
while (!deque.isEmpty()) {
str = deque.pop() + str;
}
return str;
}
}
|
拿字符串直接作为栈，省去了栈还要转为字符串的操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public String removeDuplicates(String s) {
StringBuffer res = new StringBuffer();
int top = -1;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (top >= 0 && res.charAt(top) == c) {
res.deleteCharAt(top);
top--;
} else {
res.append(c);
top++;
}
}
return res.toString();
}
}
|
150. 逆波兰表达式求值※
建议：
题目链接： https://leetcode.cn/problems/evaluate-reverse-polish-notation/
文章讲解： https://programmercarl.com/0150.%E9%80%86%E6%B3%A2%E5%85%B0%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%B1%82%E5%80%BC.html
https://www.yuanql.top/2023/07/05/02_leetcode/150.%20%E9%80%86%E6%B3%A2%E5%85%B0%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%B1%82%E5%80%BC/
题目分析
方案一
利用栈实现此功能
1
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
| class Solution {
public int evalRPN(String[] tokens) {
int result = 0;
int temp1, temp2;
Deque<Integer> deque = new ArrayDeque<>();
for (String st :
tokens) {
switch (st) {
case "+":
temp2 = deque.pop();
temp1 = deque.pop();
deque.push(temp1 + temp2);
break;
case "-":
temp2 = deque.pop();
temp1 = deque.pop();
deque.push(temp1 - temp2);
break;
case "*":
temp2 = deque.pop();
temp1 = deque.pop();
deque.push(temp1 * temp2);
break;
case "/":
temp2 = deque.pop();
temp1 = deque.pop();
deque.push(temp1 / temp2);
break;
default:
deque.push(Integer.valueOf(st));
}
}
return deque.pop();
}
}
|
结果
解答成功:
执行耗时:4 ms,击败了96.34% 的Java用户
内存消耗:41.9 MB,击败了45.47% 的Java用户
分析
时间复杂度：
O( n )
空间复杂度：
O( n )
代码随想录
https://programmercarl.com/0150.%E9%80%86%E6%B3%A2%E5%85%B0%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%B1%82%E5%80%BC.html
递归就是用栈来实现的。
所以栈与递归之间在某种程度上是可以转换的！ 这一点我们在后续讲解二叉树的时候，会更详细的讲解到。
那么来看一下本题，其实逆波兰表达式相当于是二叉树中的后序遍历。 大家可以把运算符作为中间节点，按照后序遍历的规则画出一个二叉树。
但我们没有必要从二叉树的角度去解决这个问题，只要知道逆波兰表达式是用后序遍历的方式把二叉树序列化了，就可以了。
在进一步看，本题中每一个子表达式要得出一个结果，然后拿这个结果再进行运算，那么这岂不就是一个相邻字符串消除的过程，和1047.删除字符串中的所有相邻重复项 (opens new window)中的对对碰游戏是不是就非常像了。
如动画所示：
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> stack = new LinkedList();
for (String s : tokens) {
if ("+".equals(s)) {
stack.push(stack.pop() + stack.pop());
} else if ("-".equals(s)) {
stack.push(-stack.pop() + stack.pop());
} else if ("*".equals(s)) {
stack.push(stack.pop() * stack.pop());
} else if ("/".equals(s)) {
int temp1 = stack.pop();
int temp2 = stack.pop();
stack.push(temp2 / temp1);
} else {
stack.push(Integer.valueOf(s));
}
}
return stack.pop();
}
}
|