括号匹配问题
有效的括号
20. 有效的括号 - 力扣（LeetCode）
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
提示：
1 <= s.length <= 104s仅由括号'()[]{}'组成
利用HashMap
public boolean isValid(String s)
{
HashMap<Character, Character> hashMap = new HashMap<>();
//key为左括号，value为右括号
hashMap.put('(',')');
hashMap.put('[',']');
hashMap.put('{','}');
ArrayDeque<Character> stack = new ArrayDeque<>();
for (int i = 0; i < s.length(); i++)
{
char c = s.charAt(i);
if(hashMap.containsKey(c)) //c是左括号
stack.push(c); //左括号入栈
else //c是右括号
{
//栈空，或者该右括号与栈顶的左括号不匹配
if (stack.isEmpty() || c != hashMap.get(stack.peek()))
return false;
else //匹配
stack.pop(); //栈顶的左括号出栈
}
}
//循环结束后，若栈空则s是括号有效的字符串，否则说明还有左括号没匹配
return stack.isEmpty();
}
非HashMap版
public boolean isLeftBracket(char c)
{
return c == '(' || c == '{' || c == '[';
}
public char partner(char c)
{
switch(c)
{
case ')': return '(';
case '}': return '{';
case ']': return '[';
default: return ' ';
}
}
public boolean isValid(String s)
{
//括号总数必须是偶数
if(s.length() % 2 != 0)
return false;
Stack<Character> stack = new Stack<>();
for(int i = 0; i < s.length(); i++)
{
char c = s.charAt(i);
if(isLeftBracket(c)) //c是左括号
stack.push(c);
else //c是右括号
{
//栈空，或者该右括号与栈顶的左括号不匹配
if(stack.isEmpty() || stack.peek() != partner(c))
return false;
else //匹配
stack.pop(); //栈顶的左括号出栈
}
}
return stack.isEmpty(); //栈空则s是括号有效的字符串，栈不空说明还有左括号没匹配
}
括号生成
22. 括号生成 - 力扣（LeetCode）
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
提示：
1 <= n <= 8
深搜，做减法
public List<String> generateParenthesis(int n)
{
//特判
if (n == 0)
return null;
//结果集
ArrayList<String> res = new ArrayList<String>();
//深搜，找出全部有效括号组合
DFS(res, n, n, "");
return res;
}
/**
* @param res 结果集
* @param left 左括号还能用几个
* @param right 右括号还能用几个
* @param curStr 当前递归所得到的字符串
*/
public static void DFS(List<String> res, int left, int right, String curStr)
{
//递归终止；将一种组合添加到结果集
if (left == 0 && right == 0)
{
res.add(curStr);
return;
}
//尝试使用右括号后，若左括号剩余数量大于右括号剩余数量，则“剪枝”（否则会违背有效括号的定义）
if (left > right)
return;
//优先使用左括号
if (left > 0)
DFS(res, left - 1, right, curStr + "(" );
//使用右括号
if (right > 0)
DFS(res, left, right - 1, curStr +")" );
}
深搜，做加法
public List<String> generateParenthesis(int n)
{
//特判
if (n == 0)
return null;
//结果集
ArrayList<String> res = new ArrayList<String>();
//深搜,寻找全部有效括号组合
DFS(res, 0, 0, "", n);
return res;
}
/**
* @param res 结果集
* @param left 左括号使用了几个
* @param right 右括号使用使用了几个
* @param curStr 当前递归所得到的字符串
* @param n 题目所给的括号生成对数
*/
public static void DFS(List<String> res, int left, int right, String curStr, int n)
{
//递归终止；将一种组合添加到结果集
if (left == n && right == n)
{
res.add(curStr);
return;
}
//尝试使用右括号后，若左括号使用数量小于右括号使用数量，则“剪枝”（否则会违背有效括号的定义）
if (left < right)
return;
//优先使用左括号
if (left < n)
DFS(res, left + 1, right, curStr + "(", n);
//使用右括号
if (right < n)
DFS(res, left, right + 1, curStr +")", n);
}
广搜
/**
* 队列结点
*/
class Node
{
String curStr;
int left; //左括号还剩几个没用
int right; //右括号还剩几个没用
public Node(String curStr, int left, int right)
{
this.curStr = curStr;
this.left = left;
this.right = right;
}
}
public List<String> generateParenthesis_3(int n)
{
//特判，否则n==0时下面的算法会返回""
if(n == 0)
return null;
//结果集
ArrayList<String> res = new ArrayList<String>();
ArrayDeque<Node> queue = new ArrayDeque<>();
//初始结点入队
queue.offer(new Node("", n, n));
while (!queue.isEmpty())
{
//队头元素出队
Node curNode = queue.poll();
//生成了一组有效括号
if(curNode.left == 0 && curNode.right == 0)
res.add(curNode.curStr);
//优先使用左括号
if (curNode.left > 0)
queue.offer(new Node(curNode.curStr + "(", curNode.left - 1, curNode.right));
//左括号少于右括号的情况下，才能使用右括号
if (curNode.right > 0 && curNode.left < curNode.right)
queue.offer(new Node(curNode.curStr + ")", curNode.left, curNode.right - 1));
}
return res;
}
最小栈
155. 最小栈 - 力扣（LeetCode）
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack()初始化堆栈对象。void push(int val)将元素val推入堆栈。void pop()删除堆栈顶部的元素。int top()获取堆栈顶部的元素。int getMin()获取堆栈中的最小元素。
示例 1:
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
提示：
-231 <= val <= 231 - 1pop、top和getMin操作总是在 非空栈 上调用push,pop,top, andgetMin最多被调用3 * 104次
解
建立一个存储val的元素栈和一个辅助栈，辅助栈与元素栈同步push和pop，并存储每个val入栈后对应的最小值
以空间换时间
ArrayDeque<Integer> stack; //元素栈
ArrayDeque<Integer> minStack; //辅助栈
public MinStack()
{
stack = new ArrayDeque<>();
minStack = new ArrayDeque<>();
minStack.push(Integer.MAX_VALUE);
}
public void push(int val)
{
stack.push(val);
minStack.push(Math.min(minStack.peek(), val));
}
public void pop()
{
stack.pop();
minStack.pop();
}
public int top()
{
return stack.peek();
}
public int getMin()
{
return minStack.peek();
}
最大栈
716. 最大栈 - 力扣（LeetCode）
题目要求与【最小栈】基本相同，难度提升在于要我们实现**“popMax()：检索并返回栈中最大元素，并将其移除。如果有多个最大元素，只要移除最靠近栈顶的那个。”**，以及数据增强，对时间效率要求更高
元素栈+辅助栈
对时间要求不严格的情况下，可以沿用最小栈的解法，并建立一个临时栈实现popMax()
public class MaxStack
{
ArrayDeque<Integer> stack; //元素栈
ArrayDeque<Integer> maxStack; //辅助栈
public MaxStack()
{
stack = new ArrayDeque<>();
maxStack = new ArrayDeque<>();
maxStack.push(Integer.MIN_VALUE);
}
public void push(int x)
{
stack.push(x);
maxStack.push(Math.max(maxStack.peek(), x));
}
public int pop()
{
maxStack.pop();
return stack.pop();
}
public int top()
{
return stack.peek();
}
public int peekMax()
{
return maxStack.peek();
}
public int popMax()
{
int max = peekMax();
ArrayDeque<Integer> tempStack = new ArrayDeque<>();
//将元素栈stack中在最大元素之上的所有元素一次倾倒、存储起来。辅助栈需要同步操作
while (top() != max )
tempStack.push(pop());
//找到距离栈顶最近的最大元素，删除它
pop();
//将临时栈中的元素倒回去
while (!tempStack.isEmpty())
push(tempStack.pop());
return max;
}
}
用链表结点同时存储val和max
逻辑与第一种解法一致，但一样无法通过最后一个严格的测试用例
class Node
{
int val; //元素的值
int max; //此时的最大值
Node next;
public Node(int val, int max, Node next) {
this.val = val;
this.max = max;
this.next = next;
}
}
class MaxStack_2
{
Node head = null; //指向表首元素
public MaxStack_2(){}
public void push(int x)
{
if (head == null)
head = new Node(x, x, null);
else //x与之前的最大值比较，得出新的最大值
head = new Node(x, Math.max(head.max, x), head);
}
public int pop()
{
int val = head.val;
head = head.next;
return val;
}
public int top()
{
return head.val;
}
public int peekMax()
{
return head.max;
}
public int popMax()
{
int Max = head.max;
Node tempList = null; //临时链表的头指针，作用与临时栈的栈顶指针相同
while (head.val != Max)
{
Node suc = head.next;
head.next = tempList;
tempList = head;
head = suc;
}
//删除最大元素
head = head.next;
//“倒回去”
while (tempList != null)
{
push(tempList.val);
tempList = tempList.next;
}
return Max;
}
}
