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