每日一题：Leetcode20 有效的括号
文章目录
系列：栈专练
语言：java
题目来源：leetcode20 有效的括号
难度：简单
考点：栈的理解 & 应用
思路和参考答案
- 文章目录
- 题目描述
- 一、思路
- 二、参考代码
题目描述
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号
示例 1：
输入：s = “()”
输出：true
示例 2：
输入：s = “()[]{}”
输出：true
示例3：
输入：s = “(]”
输出：false
提示：
1 <= s.length <= 10^4
s 仅由括号 ‘()[]{}’ 组成
一、思路
对称匹配问题，非常适合使用栈来解决；
方法选择：通常不使用Stack类来定义栈，使用性能更优的双端队列接口Deque来定义栈，实现类ArrayDeque/LinkedList来进行初始化
Deque deque = new ArrayDeque<>();
Deque deque = new LinkedList<>();
有关栈的一些方法：
pop() : 出栈 删除栈顶元素
push(): 入栈 元素压入栈顶
peek(): 查看栈顶元素
isEmpty(): 判断栈是否为空
本文我们使用实现LinkedList类解答；
解题思路：看到题目后很容易想到使用栈来解决问题，但是我们该怎么去着手呢？怎样去通过栈操作来实现匹配呢？
首先是字符串的长度，如果字符串为奇数，则返回false；另一种情况当然是符合题意的偶数段字符串长度，然后分为三种情况，一种是左边符号多( ‘(((}’ ),第二种是右边符号多( ‘()))’ )，第三种是一样多但是括号不匹配( "((]] ).
我们这里通过一个for循环来进行遍历字符串，通过if语句来对三种情况以及其他情况进行判断，if条件判断
举一个例子：每当有一个左括号时，栈里就push()入一个对应的右括号，一次遍历，此时栈内元素为（ “)))”）当s.charAt(i) =='}‘时，栈内没对应元素，返回false ；如果是( ‘((()’ ), 当s.charAt(i) ==’)'时，栈内有元素，弹出栈顶元素，栈内元素为（ ‘))’） ，此时字符串里没有对应的右括号来匹配，所以返回fasle；如果是 ( ‘()))’ )，此时栈内元素为 （ ‘)’ ），当for循环遍历匹配了一个右括号时，弹出后，栈内没有元素，栈为空，此时还有两个）没有被匹配，所以此时返回false；同时如果当s.charAt(i) != deque.peek() 时，也是返回false，参考代码更容易来理解
二、参考代码
双指针–滑动窗口：
class Solution {public boolean isValid(String s) {
// 栈的使用：
// 使用Deque来定义栈 Deque代替使用Stack 性能更优
// 同时可以使用ArrayDeque和LinkedList
// 当字符串长度为奇数的时候，不满足题意，所以直接返回falseif(s.length() % 2 != 0){return false;}
// 使用Deque来定义栈 Deque deque = new LinkedList<>();char ch;
// 通过for循环一次对字符进行情况匹配for(int i =0;iif(s.charAt(i) == '('){deque.push(')');}else if(s.charAt(i) == '{'){deque.push('}');}else if(s.charAt(i) == '['){deque.push(']');// 当字符在匹配完，此时栈内为空了，则说明右括号多了，则返回false 同时还有右括号和栈顶元素不匹配，同样返回false}else if(deque.isEmpty() || s.charAt(i) != deque.peek()){return false;}else{// **这里的else的条件时 s.charAt(i) = deque.peek()情况**，因为已经判断过不相等的情况了 ，这里是三种右括号匹配时的情况判断， deque.pop();}}// 如果都匹配，则栈内元素为空 返回true ，如果情况为：左括号多了 ，栈内元素不为空，此时返回false return deque.isEmpty();}}
创作不易：感谢您的一键三连！希望对您有所帮助