LeetCode：20. 有效的括号
LeetCode：20. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
示例 ：
输入：s = "()"
输出：true
我们遍历给定的字符串 s。当我们遇到一个左括号时，我们会期望在后续的遍历中，有一个相同类型的右括号将其闭合。由于后遇到的左括号要先闭合，因此我们可以将这个左括号放入栈顶。
class Solution { public boolean isValid(String s) { //长度必然是偶数
if(s.length()%2 !=0){ return false;
}
Deque<Character> stack = new LinkedList<>();
Map<Character,Character> map = new HashMap<>();
map.put(')','(');
map.put(']','[');
map.put('}','{'); for(int i=0;i<s.length();i++){
Character curr = s.charAt(i); //如果当前是右括号，则从栈中取出顶点做比较
if(map.containsKey(curr)){ if(stack.isEmpty() || stack.peek() != map.get(curr)){ return false;
}
stack.pop();
}else { //如果是左括号，则压入栈； stack.push(curr);
}
} return stack.isEmpty();
}
}
时间复杂度：O(n)，空间复杂度：O(n)
来源https://www.cnblogs.com/daxiaq/p/14781375.html