有效括号的栈的实现
1. 有效的括号Ⅰ
有“()”,"[]","{}"三种括号
public boolean isValid(String s){
Deque<Character> deque = new LinkedList<>();
char ch;
for(int i = 0; i < s.length(); i++){
ch = s.charAt(i);
//碰到左括号，就把相应的右括号入栈
if(ch == '('){
deque.push(')');
}else if(ch == '{'){
deque.push('}');
}else if(ch =='['){
deque.push(']');
}else if(deque.isEmpty() || deque.peek() != ch){
return false;
}else{
deque.pop();
}
}
return deque.isEmpty();
}
2. 有效的括号Ⅱ
有,(,)三种，可以任意匹配或不匹配
在有星号的情况下，需要两个栈分别存储左括号和星号。从左到右遍历字符串，进行如下操作。
如果遇到左括号，则将当前下标存入左括号栈。
如果遇到星号，则将当前下标存入星号栈。
如果遇到右括号，则需要有一个左括号或星号和右括号匹配，由于星号也可以看成右括号或者空字符串，因此当前的右括号应优先和左括号匹配，没有左括号时和星号匹配：
如果左括号栈不为空，则从左括号栈弹出栈顶元素；
如果左括号栈为空且星号栈不为空，则从星号栈弹出栈顶元素；
如果左括号栈和星号栈都为空，则没有字符可以和当前的右括号匹配，返回false。
遍历结束之后，左括号栈和星号栈可能还有元素。为了将每个左括号匹配，需要将星号看成右括号，且每个左括号必须出现在其匹配的星号之前。当两个栈都不为空时，每次从左括号栈和星号栈分别弹出栈顶元素，对应左括号下标和星号下标，判断是否可以匹配，匹配的条件是左括号下标小于星号下标，如果左括号下标大于星号下标则返回。
最终判断左括号栈是否为空。如果左括号栈为空，则左括号全部匹配完毕，剩下的星号都可以看成空字符串，此时 s 是有效的括号字符串，返回true。如果左括号栈不为空，则还有左括号无法匹配，此时 s 不是有效的括号字符串，返回 false。
class Solution{
public boolean checkValidString(String s){
Deque<Integer> leftStack = new LinkedList<Integer>();
Deque<Integer> asteriskStack = new LinkedList<Integer>();
int n = s.length();
for(int i = 0; i < n; i++){
char c = s.charAt(i);
if(c == '('){
leftStack.push(i);
}else if(c == '*'){
asteriskStack.push(i);
}else{
if(!leftStack.isEmpty()){
leftStack.pop();
}else if(!asteriskStack.isEmpty()){
asteriskStack.pop();
}else{
return false;
}
}
}
while(!leftStack.isEmpty() && !asteriskStack.isEmpty()){
int leftIndex = leftStack.pop();
int asteriskIndex = asteriskStack.pop();
if(leftIndex > asteriskIndex){
return false;
}
return leftStack.isEmpty();
}
}
}
3. 有效括号字符串Ⅲ
最长有效括号字符串，仅有'('和')'
具体做法是我们始终保持栈底元素为当前已经遍历过的元素中「最后一个没有被匹配的右括号的下标」，这样的做法主要是考虑了边界条件的处理，栈里其他元素维护左括号的下标：
对于遇到的每个‘(’ ，我们将它的下标放入栈中
对于遇到的每个 ‘)’ ，我们先弹出栈顶元素表示匹配了当前右括号：
我们从前往后遍历字符串并更新答案即可。
如果栈为空，说明当前的右括号为没有被匹配的右括号，我们将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」
如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」
需要注意的是，如果一开始栈为空，第一个字符为左括号的时候我们会将其放入栈中，这样就不满足提及的「最后一个没有被匹配的右括号的下标」，为了保持统一，我们在一开始的时候往栈中放入一个值为 −1 的元素。
class Solution {
public int longestValidParentheses(String s) {
int maxans = 0;
Deque<Integer> stack = new LinkedList<Integer>();
stack.push(-1);
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(i);
} else {
stack.pop();
if (stack.isEmpty()) {
stack.push(i);
} else {
maxans = Math.max(maxans, i - stack.peek());
}
}
}
return maxans;
}
}
原文链接：https://www.dianjilingqu.com/441422.html
