刷题日记

括号匹配

题目描述

20. 有效的括号 - 力扣（LeetCode）

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = “()”
输出：true

示例 2：

输入：s = “()[]{}”
输出：true

示例 3：

输入：s = “(]“
输出：false

提示：

  • 1 <= s.length <= 10<sup>4</sup>
  • s 仅由括号 '()[]{}' 组成

第一想法就是Stack，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.Stack;

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '{' || ch == '[' || ch == '(') stack.push(ch);
            if (ch == '}') {
                if (!stack.empty()&&stack.peek() == '{') stack.pop();
                else return false;
            }
            if (ch == ']') {
                if (!stack.empty()&&stack.peek() == '[') stack.pop();
                else return false;
            }
            if (ch == ')') {
                if (!stack.empty()&&stack.peek() == '(') stack.pop();
                else return false;
            }
        }
        return stack.empty();
    }
}

确实不错，可惜

image-20240427235816885

image-20240428000016467

仔细查看了前面几位大佬的代码，选取了一个可读性较高且比较简洁的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean isValid(String s) {
        char[] stack = new char[s.length()];
        int top = -1;//栈顶指针
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack[++top] = ')';
            } else if (c == '[') {
                stack[++top] = ']';
            } else if (c == '{') {
                stack[++top] = '}';
            } else if (top == -1 || stack[top--] != c) {//之前没有对应的左括号或者左右括号不匹配
                return false;
            }
        }
        return top == -1;//判断是否有剩余的左括号没有被匹配
    }
}

只看规格的话二者都是 $ O(N) $ 的时间复杂度，使用工具查看下具体逻辑运行时间。

1
2
3
4
String test = "{".repeat(100000000);
Examination.start();
System.out.println("isValid(): "+isValid(test));
Examination.end();

使用长度为1亿的字符串进行遍历，我的算法耗时执行时间为：3698.19 ms, 消耗内存：969.07 M + !。

案例算法耗时执行时间为：176.65 ms, 消耗内存：382.88 M + !

测试字符串 我的算法 改进算法
10 时间为：3.85 ms, 消耗内存：0.00 M + ! 时间为：4.30 ms, 消耗内存：0.00 M + !
100 时间为：4.28 ms, 消耗内存：0.15 M + ! 时间为：3.57 ms, 消耗内存：0.00 M + !
1000 时间为：4.23 ms, 消耗内存：0.15 M + ! 时间为：4.03 ms, 消耗内存：0.15 M + !
10，000 时间为：4.16 ms, 消耗内存：0.15 M + ! 时间为：4.07 ms, 消耗内存：0.15 M + !
100，000 时间为：8.05 ms, 消耗内存：1.09 M + ! 时间为：6.04 ms, 消耗内存：1.15 M + !
1，000，000 时间为：29.81 ms, 消耗内存：14.82 M + ! 时间为：10.18 ms, 消耗内存：4.93 M + !
10，000，000 时间为：220.47 ms, 消耗内存：95.30 M + ! 时间为：28.97 ms, 消耗内存：40.15 M + !
100，000，000 时间为：2804.93 ms, 消耗内存：968.63 M + ! 时间为：175.74 ms, 消耗内存：382.42 M +
1,000，000，000 Exception in thread "main" java.lang.OutOfMemoryError:
Java heap space		 时间为：1583.38 ms, 消耗内存：3821.84 M + !
2，000，000，000 Exception in thread "main" java.lang.OutOfMemoryError:
Java heap space

这个算法优化得相当不错，字符串长度为1billlion的情况下甚至只用了1.5s,消耗内存3.7G.

空间复杂度分析

我的算法申请了两个变量：长度为length的stack、局域变量char ch。案例算法只申请了一个变量：长度为length的stack数组。

$每次循环申请的内存=\frac{总消耗内存}{length}$

我的算法每次申请了10Byte的空间，案例算法每次申请了4Byte的空间。

replace后者发现空间复杂度无明显变化，那就

Java之sizeof()问题_java的sizeof是什么-CSDN博客

我的博客日记 - 新逆 - 博客园 (cnblogs.com)

时间复杂度分析