系列文章目录
目录
20. 有效的括号
（1）不匹配的情况分为三类：①多了左括号，②多了右括号，③左右括号不匹配。
（2）每当遇到了左括号，就把对应的右括号（方便后面比较）加入栈内（用栈就可以保证后进去的可以先进行匹配，符合对称逻辑）。如果遇到了右括号，那么就与栈内的元素进行比较。最终出现的情况：遍历完了栈还有元素（多左），还没遍历完栈已经空了（多右），遍历元素与栈顶元素不相等（左右不匹配）。
利用栈对称匹配
开头可以先对字符串长度进行判断，因为如果长度不是偶数，那么一定是不匹配的括号。
import java.util.Stack;
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public boolean isValid(String s) {
if (s.length() % 2 != 0) {// 如果s的长度为奇数，一定不符合要求
return false;
}
Stack<Character> st = new Stack<>();
char ch;
for (int i = 0; i < s.length(); i++) {
ch = s.charAt(i);
if (ch == '(') {
st.push(')');
} else if (s.charAt(i) == '{') {
st.push('}');
} else if (s.charAt(i) == '[') {
st.push(']');
} else if (st.isEmpty() || st.peek() != ch) {
//①：遍历字符串匹配的过程中，栈空了，说明多了右括号
//②遍历字符串匹配的过程中，发现栈里没有我们要匹配的字符。即左右括号不匹配
return false;
} else {
st.pop();
}
}
//最后判断栈中元素是否匹配，如果不为空，说明多了左括号
return st.isEmpty();
}
}
//leetcode submit region end(Prohibit modification and deletion)
将栈中元素弹出与判断栈顶元素是否匹配分开，比较耗时（2ms)：
else if (st.isEmpty() || /*st.pop()*/st.peek() != ch) {
//①：遍历字符串匹配的过程中，栈空了，说明多了右括号
//②遍历字符串匹配的过程中，发现栈里没有我们要匹配的字符。即左右括号不匹配
return false;
} else {
st.pop();
}
若将栈中元素弹出与判断栈顶元素是否匹配放一起，比较节省时间(1ms)：
else if (st.isEmpty() || st.pop() != ch) {
//①：遍历字符串匹配的过程中，栈空了，说明多了右括号
//②遍历字符串匹配的过程中，发现栈里没有我们要匹配的字符。即左右括号不匹配
return false;
}
1047. 删除字符串中的所有相邻重复项
①使用 Deque 作为堆栈
（1）Deque是双端队列，两端都可以进出。Deque堆栈操作方法：push()、pop()、peek()。
push()：将元素推送到由此deque表示的堆栈（换句话说，在此deque的头部），如果当前没有可用空间，则抛出IllegalStateException异常。
此方法相当于addFirst() 。
pop()：从这个deque表示的堆栈中弹出一个元素。 换句话说，删除并返回此deque的第一个元素。
peek()：检索但不删除由此deque表示的队列的头部（换句话说，该deque的第一个元素），如果此deque为空，则返回null 。
（2）基本数据类型转String类型，只需将基本数据类型的值+“”。
（3）加入栈的条件：deque.isEmpty() || deque.peek() != ch，①栈为空。②当前元素不等于栈顶元素。
import java.util.ArrayDeque;
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public String removeDuplicates(String s) {
//ArrayDeque会比LinkedList在除了删除元素这一点外会快一点
//参考：https://stackoverflow.com/questions/6163166/why-is-arraydeque-better-than-linkedlist
ArrayDeque<Character> deque = new ArrayDeque<>();
char ch;
for (int i = 0; i < s.length(); i++) {
ch = s.charAt(i);
if (deque.isEmpty() || deque.peek() != ch) {
deque.push(ch);
} else {
deque.pop();
}
}
//基本数据类型转String类型，只需将基本数据类型的值+""。
String str = "";
while (!deque.isEmpty()) {
str = deque.pop() + str;//字符串拼接的同时实现反转
}
return str;
}
}
//leetcode submit region end(Prohibit modification and deletion)
②双指针法（使用快慢指针）比用栈快很多
class Solution {
public String removeDuplicates(String s) {
char[] ch = s.toCharArray();
int fast = 0;
int slow = 0;
for (fast = 0; fast < ch.length; fast++) {
//while(fast <ch.length()){
// 直接用fast指针所指向的元素的值覆盖slow指针的值
ch[slow] = ch[fast];
// 遇到前后相同值的，就跳过，即slow指针后退一步，下次循环就可以直接被覆盖掉了
//此时为slow-1，即指向第一个重复的元素，在下一次循环中，
// 由于fast指向两个重复项的后一个元素，就将该元素赋值给第一个重复的元素的位置即slow-1。
if (slow > 0 && ch[slow] == ch[slow - 1]) {
slow--;
} else {
slow++;
}
//fast++;//与while配合使用
}
return new String(ch,0,slow);
}
}
