【算法系列-栈与队列】栈解决匹配消除问题

1. 算法分析🛸

栈能够应用于许多匹配消除的场景，如括号匹配、删除相邻重复项等，就像在玩游戏中的消除对对碰一样，在这些场景下合理运用栈来匹配消除的对象是比较高效的！接下来就来几道题试一试：

2. 有效的括号(LeetCode 20)

【题目链接】20. 有效的括号 - 力扣（LeetCode）

2.1 思路分析🎯

这是一道很经典的题目，可以通过栈来解决这道题，同时可以有两种思路：

• 左括号入栈
• 右括号入栈

左括号入栈便是在匹配到左括号时将该元素加入栈，匹配到右括号时则将判断栈顶元素是否能与当前右括号组合成一个完整的括号，思路比较好理解

2.2 代码示例🌰

class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();for (int i = 0;i < s.length();i++) {char c = s.charAt(i);if (c == '(' || c == '{' || c == '[') {stack.push(c);}else {if (stack.isEmpty()) {return false;}char pc = stack.peek();String str = "" + pc + c;if (str.equals("()") || str.equals("{}") || str.equals("[]")) {stack.pop();}else {return false;}}}return stack.isEmpty();}
}

与左括号入栈不同，这里使用右括号入栈

当匹配到左括号时，将该左括号对应的右括号入栈；

当匹配到右括号时：

• 判断当前栈是否为空，为空则返回false；

• 若不为空，判断是否与栈顶元素相同：

• • 不同则表示前面没有出现与当前右括号匹配的左括号(注：因为我们前面是选择将右括号入栈，所以匹配的是右括号)
  • 相同则表示前面出现过与之匹配的左括号，将其弹出栈

直到循环结束，判断当前栈是否为空，空则返回true，反之返回false

代码如下：

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

3. 删除字符串中的相邻重复项(LeetCode 1047)

【题目链接】1047. 删除字符串中的所有相邻重复项 - 力扣（LeetCode）

3.1 思路分析🎯

与括号匹配思路一致，只是将对括号进行匹配换成了对字符进行匹配

3.2 代码示例🌰

class Solution {public String removeDuplicates(String s) {Stack<Character> stack = new Stack<>();for (int i = 0;i < s.length();i++) {char c = s.charAt(i);if (stack.isEmpty()) {stack.push(c);}else if (stack.peek() == c) {stack.pop();}else {stack.push(c);}}StringBuffer sub = new StringBuffer();while (!stack.isEmpty()) {sub.insert(0, stack.pop());}return sub.toString();}
}

4. 逆波兰表达式(LeetCode 150)

【题目链接】150. 逆波兰表达式求值 - 力扣（LeetCode）

4.1 思路分析🎯

理清楚逆波兰表达式的概念后，思路与上述两道题一致，都是匹配元素发生更换但过程一致

4.2 代码示例🌰

class Solution {public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<>();for (String s : tokens) {int x = 0, y = 0;if (s.equals("+")) {x = stack.pop();y = stack.pop();stack.push(y + x);}else if (s.equals("-")) {x = stack.pop();y = stack.pop();stack.push(y - x);}else if (s.equals("*")) {x = stack.pop();y = stack.pop();stack.push(y * x);}else if (s.equals("/")) {x = stack.pop();y = stack.pop();stack.push(y / x);}else {stack.push(Integer.valueOf(s));}}return stack.peek();}
}

以上便是对栈解决匹配消除问题的介绍了！！后续还会继续分享其它算法系列内容，如果这些内容对大家有帮助的话请给一个三连关注吧💕( •̀ ω •́ )✧( •̀ ω •́ )✧✨