算法：有效括号
版权声明： https://blog.csdn.net/li_xunhuan/article/details/90140416
问题描述：
给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。
示例 1:
输入: “()” 输出: true
示例 2:
输入: “()[]{}” 输出: true
示例 3:
输入: “(]” 输出: false
示例 4:
输入: “([)]” 输出: false
示例 5:
输入: “{[]}” 输出: true
方案1：
我们用一个堆栈来实现，若发现是左括号之一，压入堆栈；发现是右括号之一，那么弹出上一个堆栈值，除非弹出括号是与当前右括号对应的左括号，那么必然是括号不对； 这样我们还要考虑一个问题，如果左括号比右括号多怎么办，但是存在着的右括号和左括号都是匹配的，那么我们考虑到，堆栈的弹出左括号操作必然会有造成栈元素减少，所以我们利用堆栈元素空不空来最后把关，是否完全匹配
时间复杂度，空间复杂度：均为O(n)
代码1：
class Solution {
public boolean isValid(String s) {
if(s==null){
return false;
}
int length=s.length();
if(length==0)
return true;Stack stack = new Stack<>();
for(int i=0;i<length;i++){
char charTemp=s.charAt(i);
if(charTemp=='{'||charTemp=='['||charTemp=='('){
stack.push(charTemp);
}else{
if(stack.empty())
return false;
char charcurr = stack.pop();
if((charTemp=='}'&&charcurr!='{')||(charTemp==']'&&charcurr!='[')||(charTemp==')'&&charcurr!='('))
return false;
}
}
if(stack.empty())
return true;
return false;
}
}方案2：
我们发现使用Java语法中的Stack结构可以解决这个问题，那么问题来了，我们何不用简单的数组实现这个问题，只要设置一个top指针（Java中没有指针，但是类似于C中的作用，所以命名为指针），使top始终指向堆栈顶元素，并且自定义数组实现堆栈的压入push以及弹出操作pop 时间复杂度，空间复杂度：均为O(n)
代码2：
class Solution {
public boolean isValid(String s) {
if(s==null){
return false;
}
int length=s.length();
if(length==0)
return true;
char[] stack=new char[length];
int top=-1;
for(int i=0;i<length;i++){
char charTemp=s.charAt(i);
if(charTemp=='{'||charTemp=='['||charTemp=='('){
++top;
stack[top]=charTemp;
}else{
if(top==-1)
return false;
char charcurr = stack[top];
top--;
if((charTemp=='}'&&charcurr!='{')||(charTemp==']'&&charcurr!='[')||(charTemp==')'&&charcurr!='('))
return false;
}
}
if(top==-1)
return true;
return false;
}
}方案3：
我们发现如果数组用不了这么大，这样造成了空间的极大浪费，所以我们用ArrayList对方案2中的数组数据结构进行优化： 时间复杂度，空间复杂度：均为O(n)
实际上这个运行时间并不比方案2简单，原因暂时未知
代码3：
class Solution {
public boolean isValid(String s) {
if(s==null){
return false;
}
int length=s.length();
if(length==0)
return true;
List<Character> stack= new ArrayList<>();
for(int i=0;i<length;i++){
char charTemp=s.charAt(i);
if(charTemp=='{'||charTemp=='['||charTemp=='('){
stack.add(charTemp);
}else{
if(stack.isEmpty())
return false;
char charcurr = stack.remove(stack.size()-1);
if((charTemp=='}'&&charcurr!='{')||(charTemp==']'&&charcurr!='[')||(charTemp==')'&&charcurr!='('))
return false;
}
}
if(stack.isEmpty())
return true;
return false;
}
}