一、括号匹配问题
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。有效字符串需满足：(1)左括号必须用相同类型的右括号闭合。(2)左括号必须以正确的顺序闭合。注意：空字符串可被认为是有效字符串。
解题思路：遇到左括号就入栈，如果遇到右括号则取出栈顶元素，看看栈顶元素和当前元素是否匹配，如果字符串遍历完后，同时栈也为空，则为匹配的情况。
完整代码：
class Solution { public boolean isValid(String s) { //1.创建一个栈 Stack<Character> stack = new Stack<Character>(); //2.循环遍历每个字符 for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); //3.如果是左括号就入栈 if(c=='(' || c=='[' || c=='{') { stack.push(c); continue; } //4.如果是右括号就取出栈顶元素 if(stack.isEmpty()) { return false; } char top = stack.pop(); //5.检查当前元素是否匹配 if(top == '(' && c == ')') { continue; } if(top == '[' && c == ']') { continue; } if(top == '{' && c == '}') { continue; } //三种情况都不符合则为非法情况 return false; } //6.判断栈是否为空 if(stack.isEmpty()) { return true; } return false; } }运行结果：
二、最小栈问题
设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。push(x) -- 将元素 x 推入栈中。pop() -- 删除栈顶的元素。top() -- 获取栈顶元素。getMin() -- 检索栈中的最小元素。
解题思路：核心思路是空间来换时间，用额外空间把最小元素提前保存好，A用来存储栈中的数据，B专门用来存当前栈帧对应的最小元素。先把元素插入到A中，在把当前最小元素存放到B中，如果 B 不为空，当前B的栈顶元素就是之前的最小值，接下来把之前最小值与当前新元素进行对比，确定新的最小值。
注：当线程执行到某个方法时就会往方线程栈中压入一个帧，称为栈帧，栈帧中包含了方法的局部变量表、操作数栈、返回地址、动态连接等信息。
具体代码：
package package3; import java.util.Stack; public class MinStack { // A 用来表示正常栈中的数据 // B 用来存储每一层 A栈帧中对应的最小值 private Stack<Integer> A = new Stack<>(); private Stack<Integer> B = new Stack<>(); public void push(int x) { // 1. 先把元素插入到A中 A.push(x); // 2. 把当前最小元素插入到B中 if (B.isEmpty()) { B.push(x); return; } // 如果 B 不为空，当前B的栈顶元素就是之前的最小值 // 之前最小值与当前新元素进行对比，确定新的最小值 int min = B.peek(); if (x < min) { min = x; } B.push(min); } public void pop() { if (A.isEmpty()) { return; } A.pop(); B.pop(); } public int top() { return A.peek(); } public int getMin() { return B.peek(); } }运行结果：
