力扣20.有效的括号
原题，题目描述：
我们也是过渡到了栈的题，其实前面二分查找还有一个题没做🤡🤡🤡🤡。这道题比较简单，力扣分类也是简单题，不过你要是正常做，肯定拿不到百分百。
思路一
这种括号题第一个想到的就是栈，我们遇到前括号就放入栈，遇到后括号就将前括号弹出栈，然后一个个判断是不是有效括号即可。我们根据最朴素的想法直接写代码。
代码一
class Solution {
public boolean isValid(String s) {
int len = s.length();
ArrayDeque<Character> deque = new ArrayDeque<>();
for (int i = 0; i < len; ++i) {
char c = s.charAt(i);
if (deque.isEmpty()) {
deque.add(c);
continue;
}
if (c == ')') {
Character last = deque.removeLast();
if ('(' != last) {
return false;
}
continue;
}else if (c==']'){
Character last = deque.removeLast();
if ('[' != last) {
return false;
}
continue;
}else if (c=='}'){
Character last = deque.removeLast();
if ('{' != last) {
return false;
}
continue;
}
deque.addLast(c);
}
return deque.isEmpty();
}
}
很朴素，也很高效，O(N)的时间复杂度，但是提交发现只打败了百分之80，说明我们的代码还有很多可以优化的点，我们来看：
思路二
我们这里使用的栈是Java的api，其实这个在Java中表示的并不是栈，而是双端队列，只是我们当栈使用。但是问题在于我们只需要用到这个对象一小部分功能，那我们可以自己实现针对题目的栈。这里我们循环内部的代码也写得比较冗余（当然可读性杠杠的），所以我们也顺手优化一下。并且括号当然是成对存在的，我们也可以在开头判断一下字符串的长度，看看是不是双数，如果是单数直接返回。
代码二
class Solution {
public boolean isValid(String s) {
int len = s.length();
if ((len & 1) != 0)
return false;
char[] stack = s.toCharArray();
int top = -1;
for (int i = 0; i < len; ++i) {
char c = stack[i];
if (c == ')' || c == ']' || c == '}') {
if (top == -1) {
return false;
}
char last = stack[top--];
if (last != c - 2 && last != c - 1) {
return false;
}
continue;
}
stack[++top] = c;
}
return top == -1;
}
}
上面的代码看起来清爽了许多，也快了不少，但是还是没有百分百，只有百分之99。
力扣20.有效的括号
https://www.than.pw/archives/019ca39b-05c9-762e-a7b7-09e764680e64