每日一道 LeetCode (6)：有效的括号
❝每天 3 分钟，走上算法的逆袭之路。
❞
前文合集
代码仓库
GitHub：https://github.com/meteor1993/LeetCode
Gitee：https://gitee.com/inwsy/LeetCode
题目：有效的括号
题目来源：https://leetcode-cn.com/problems/valid-parentheses/
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
解题思路
解题思路？
啊呸，有个 P 的解题思路，我跟你们讲哦，这种题没见过，你就是想不出来。
我自己思索了几分钟以后，果断投降去看答案了，这玩意，不是我这种新手小白搞的定的。
结果，一看答案秒懂。
整个解题思路是借用了数据结构「栈」的「先进后出」的特性。
首先第一件事情还是先思考清楚极限情况，比如如果是空字符串，是可以返回 true ，如果字符串长度是奇数，那么显然是无法满足左右括号的对应关系。
接下来就是核心问题，一个左括号一个右括号，中间还可能隔着千山万水，如何处理？
使用「栈」结构：
遇到左括号就压入栈。 遇到右括号就和栈顶的左括号比对，匹配失败直接返回 false 。 如果匹配成功，则可能是嵌套在其它匹配括号中的，所以此时要将当前栈顶的左括号弹出。 如果最后最终，栈中没有剩余元素，也就是没有剩下左括号，说明刚好完成匹配，括号字符串有效。否则匹配失败，括号字符串无效。
如果上面这一段不好理解，可以借助下面这个动图（来源：LeetCode）：
代码实现
有了上面的思路，写代码都是小事儿了，先看一个我自己写的，完全符合上面的逻辑：
public boolean isValid(String s) {
if (s.length() == 0) return true;
if (s.length() % 2 == 1) return false;
Stack stack = new Stack<> ();
for (int i = 0; i < s.length(); i++) {
char charAt = s.charAt(i);
// 如果是左括号，则把字符压入栈
if (charAt == '(' || charAt == '{' || charAt == '[')
stack.push(charAt);
else {
// 如果此时还有右括号而栈中已无左括号
if (stack.isEmpty()) return false;
// 获取栈顶的值
char top = stack.peek();
// 如果栈顶的值等于右括号，则出栈，否则返回 false
if ((top == '{' && charAt == '}') || (top == '(' && charAt == ')') || (top == '[' && charAt == ']'))
stack.pop();
else
return false;
}
}
return stack.isEmpty();
}
里面的注释已经比较清晰了，我就不多解释了。
接着我看了官方提供的答案，基本上思路和我的代码保持一致，只是把左右括号放入到了哈希表中，由哈希表来判断括号是否存在。
private Map map;
// 初始化哈希表
public Solution() {
this.map = new HashMap<> ();
this.map.put(')', '(');
this.map.put('}', '{');
this.map.put(']', '[');
}
public boolean isValid_1(String s) {
if (s.length() == 0) return true;
if (s.length() % 2 == 1) return false;
Stack stack = new Stack<> ();
for (int i = 0; i < s.length(); i++) {
char charAt = s.charAt(i);
// 如果不是右括号，则把字符压入栈
if (!this.map.containsKey(charAt)) {
stack.push(charAt);
} else {
// 如果此时还有右括号而栈中已无左括号
if (stack.isEmpty()) return false;
// 获取栈顶的值
char top = stack.peek();
// 如果栈顶的值等于右括号，则出栈，否则返回 false
if (top == this.map.get(charAt))
stack.pop();
else
return false;
}
}
return stack.empty();
}
因为哈希表中的数据太少，而且寻址的次数也不够多，所以哈希表的方案看起来还比顺次匹配的的方案耗时高。
效率更高的方案有没有，当然有，直接使用数组模拟栈的入栈和出栈，这个时间是可以压缩在 1ms 以内的，执行时间可以在 Java 的提交中击败 100% 的用户，这个示例我就不写了，感兴趣的同学可以自己写写看。
在我翻答案的时候看到一个 1ms 的方案，这个方案是对我前面的那个 2ms 的代码的优化，有点意思，拿出来聊一下：
public boolean isValid_2(String s) {
char[] chs = s.toCharArray();
Stack stack = new Stack<>();
for (char c : chs) {
if (c == '{') {
stack.push('}');
} else if (c == '[') {
stack.push(']');
} else if (c == '(') {
stack.push(')');
} else if (stack.isEmpty() || stack.pop() != c) {
return false;
}
}
return stack.isEmpty();
}
这个方案就是在遇到左括号的时候往栈里面放一个对应的右括号，这么做的原因我猜测是为了好判断，只需要取出的时候和当前循环的右括号做一次 == 判断，如果相等就继续循环，不相等就直接返回 false 了。
不得不说这个方案的构思很巧妙，在已有的方案上做了相当极致的优化，把耗时进一步降低。果然姜还是老的辣，你大爷还是你大爷。
果然是学无止境，希望各位刷 LeetCode 的同学，如果时间充足，也可以多看看不同的答案，对开阔思路和视野真的是相当有帮助。
❝顺便吐槽下：想到这些方案的大神太 TM 变态了，这个脑回路和常人差的太远了，能用数组把耗时压到 1ms 以内我能接受，但是能把栈这种数据结构的方案优化到 2ms 以内，这个我是真的服。
❞
