LeetCode 20. 有效的括号 栈常规题解,简单题目常规练手。
20. 有效的括号#
https://leetcode.cn/problems/valid-parentheses/
给定一个只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
栈常规解法#
遍历字符串,碰到左括号就放入集合,碰到右括号,我们拿出最近的一个元素判断是否配对。
此过程符合栈结构的使用场景。
复杂度分析#
整个过程只需遍历一次字符串长度,设字符串长度为n
,时间复杂度为O(n)
。
我们使用了额外的栈来辅助决策,容器最大长度需要n/2
,空间复杂度O(n)
。
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
43
44
45
46
47
|
/*
* 执行用时:
* 1 ms
* , 在所有 Java 提交中击败了
* 98.96%
* 的用户
* 内存消耗:
* 39 MB
* , 在所有 Java 提交中击败了
* 98.54%
* 的用户
* 通过测试用例:
* 91 / 91
*/
public boolean isValid(String s) {
if (s == null || s.isEmpty() || s.length() % 2 != 0) {
return false;
}
// 使用一个栈结构保存遍历结果,给定s可以提前确定栈的最大长度,此举可提高空间效率
Deque<Character> stack = new ArrayDeque<>(s.length()/2+1);
for (char c : s.toCharArray()) {
if (c == '(' || c == '{' || c == '[') {
stack.push(c);
continue;
}
if (stack.isEmpty()) {
return false;
}
// 左括号
char left = stack.pop();
if (left == '(') {
if (c != ')') {
return false;
}
} else if (left == '[') {
if (c != ']') {
return false;
}
} else if (left == '{') {
if (c != '}') {
return false;
}
}
}
return stack.isEmpty();
}
|
如果使用基于链表的容器类,可以不考虑提前指定容量。本题我们使用了基于数组的ArrayDeque
。