LeetCode刷题Java版：020.有效的括号

作者：沉默王二
发布时间：2022-08-06T09:00:51.426+0800

终于，终于，我们的题解更新到了第 20 道，也就是 300 道中的 1/15，道阻且长，我们还需要继续坚持。我们把这份 PDF 的封面也做了出来，大家欣赏下。

020.有效的括号

题意

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

难度

简单

示例

输入：s = "(]"
输出：false

输入：s = "([)]"
输出：false

输入：s = "{[]}"
输出：true

分析

对于括号的匹配，我们可以利用栈这个数据结构来实现。为什么呢？

我们先来看百度百科对栈的定义。

栈（stack）又名堆栈，一种限定仅在表尾进行插入/删除的线性表。一端被称为栈顶，另一端称为栈底。向一个栈插入新元素称作入栈，它会把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素称作出栈，它会把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

然后我们来分析这道题。

要判断当前这个右括号是否跟它未匹配过的最近的左括号相匹配，我们可以先把这个左括号压入栈中，匹配成功后再把这个括号从栈中弹出。

ava
public class Solution {
public boolean isValid(String s) {
Stack st = new Stack<>();
for(int i = 0;i < s.length();i++){
if(s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{')
st.push(s.charAt(i));
else{
if(st.size() == 0)
return false;
char com = st.pop();
if(com == '(' && s.charAt(i) == ')'
|| com == '[' && s.charAt(i) == ']'
|| com == '{' && s.charAt(i) == '}')
continue;
else
return false;
}
}
return st.size() == 0;
}
}

倘若匹配成功，则继续向后匹配，如果不成功，则必然是个不合法的括号序列，直接返回 false。

而匹配成功仅限于以下三种情况：

当前第i位字符为(，且栈顶元素为)
当前第i位字符为[，且栈顶元素为]
当前第i位字符为{，且栈顶元素为}

当然，在整个字符串遍历了之后，我们仍然要检查一下，栈是否全部弹出，否则就代表仍有左括号没有匹配成功，也是一个不合法的括号序列。

总结

本次我们利用了栈这个数据结构来解决了括号匹配问题，实际上，栈还能解决更多问题，如表达式的转换、求值，而且通过保持栈内元素的单调性，还可以离线解决 RMQ 问题（Range Maximum/Minimum Query问题，即区间最值问题）。

力扣链接：https://leetcode.cn/problems/valid-parentheses/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对二哥编程星球的球友开放，如果你也想一起打卡学习算法的话，戳链接加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球目前已有 560 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

    ## 终于，终于，我们的题解更新到了第 20 道，也就是 300 道中的 1/15，道阻且长，我们还需要继续坚持。我们把这份 PDF 的封面也做了出来，大家欣赏下。

020.有效的括号

题意

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

难度

简单

示例

输入：s = "(]"
输出：false

输入：s = "([)]"
输出：false

输入：s = "{[]}"
输出：true

分析

对于括号的匹配，我们可以利用栈这个数据结构来实现。为什么呢？

我们先来看百度百科对栈的定义。

栈（stack）又名堆栈，一种限定仅在表尾进行插入/删除的线性表。一端被称为栈顶，另一端称为栈底。向一个栈插入新元素称作入栈，它会把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素称作出栈，它会把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

然后我们来分析这道题。

要判断当前这个右括号是否跟它未匹配过的最近的左括号相匹配，我们可以先把这个左括号压入栈中，匹配成功后再把这个括号从栈中弹出。

倘若匹配成功，则继续向后匹配，如果不成功，则必然是个不合法的括号序列，直接返回 false。

而匹配成功仅限于以下三种情况：

当前第i位字符为(，且栈顶元素为)
当前第i位字符为[，且栈顶元素为]
当前第i位字符为{，且栈顶元素为}

当然，在整个字符串遍历了之后，我们仍然要检查一下，栈是否全部弹出，否则就代表仍有左括号没有匹配成功，也是一个不合法的括号序列。

总结

力扣链接：https://leetcode.cn/problems/valid-parentheses/

一步一个脚印

PDF 版本目前只针对二哥编程星球的球友开放，如果你也想一起打卡学习算法的话，戳链接加入我们吧。

    ## 终于，终于，我们的题解更新到了第 20 道，也就是 300 道中的 1/15，道阻且长，我们还需要继续坚持。我们把这份 PDF 的封面也做了出来，大家欣赏下。

020.有效的括号

题意

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

难度

简单

示例

输入：s = "(]"
输出：false

输入：s = "([)]"
输出：false

输入：s = "{[]}"
输出：true

分析

对于括号的匹配，我们可以利用栈这个数据结构来实现。为什么呢？

我们先来看百度百科对栈的定义。

栈（stack）又名堆栈，一种限定仅在表尾进行插入/删除的线性表。一端被称为栈顶，另一端称为栈底。向一个栈插入新元素称作入栈，它会把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素称作出栈，它会把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

然后我们来分析这道题。

要判断当前这个右括号是否跟它未匹配过的最近的左括号相匹配，我们可以先把这个左括号压入栈中，匹配成功后再把这个括号从栈中弹出。

倘若匹配成功，则继续向后匹配，如果不成功，则必然是个不合法的括号序列，直接返回 false。

而匹配成功仅限于以下三种情况：

当前第i位字符为(，且栈顶元素为)
当前第i位字符为[，且栈顶元素为]
当前第i位字符为{，且栈顶元素为}

当然，在整个字符串遍历了之后，我们仍然要检查一下，栈是否全部弹出，否则就代表仍有左括号没有匹配成功，也是一个不合法的括号序列。

总结

力扣链接：https://leetcode.cn/problems/valid-parentheses/

一步一个脚印

PDF 版本目前只针对二哥编程星球的球友开放，如果你也想一起打卡学习算法的话，戳链接加入我们吧。

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412