LeetCode Hot100（42/100）——20. 有效的括号

文章目录

• • 一、题目描述
  • 二、问题分析
  • 三、核心思路
  • 四、思维导图
  • 五、算法流程图
  • 六、详细步骤解析
  • 七、Java 代码实现
  • 八、复杂度分析

题目链接：LeetCode – Valid Parentheses

一、题目描述

给定一个只包含 '('、')'、'{'、'}'、'['、']' 的字符串 s，要求判断该字符串中的括号是否成对出现且嵌套合法。

示例：

二、问题分析

判断一个括号字符串是否有效，有两个关键约束：

这个特性非常符合 栈（Stack） 的“先进后出（LIFO）”特征。

三、核心思路

我们可以使用一个栈来模拟括号的匹配过程：

• 当遇到左括号 '('、'{'、'[' 时，将其入栈；
• 当遇到右括号时，判断此时栈顶元素是否与该右括号匹配。
  • 若匹配，则弹栈；
  • 若不匹配或栈为空，则直接返回 false；
• 遍历完字符串后，若栈为空，则返回 true，否则返回 false。

四、思维导图

#mermaid-svg-lhgbKdCwloHyxOfy{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-lhgbKdCwloHyxOfy .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-lhgbKdCwloHyxOfy .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-lhgbKdCwloHyxOfy .error-icon{fill:#552222;}#mermaid-svg-lhgbKdCwloHyxOfy .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-lhgbKdCwloHyxOfy .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-lhgbKdCwloHyxOfy .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-lhgbKdCwloHyxOfy .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-lhgbKdCwloHyxOfy .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-lhgbKdCwloHyxOfy .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-lhgbKdCwloHyxOfy .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-lhgbKdCwloHyxOfy .marker{fill:#333333;stroke:#333333;}#mermaid-svg-lhgbKdCwloHyxOfy .marker.cross{stroke:#333333;}#mermaid-svg-lhgbKdCwloHyxOfy svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-lhgbKdCwloHyxOfy p{margin:0;}#mermaid-svg-lhgbKdCwloHyxOfy .edge{stroke-width:3;}#mermaid-svg-lhgbKdCwloHyxOfy .section–1 rect,#mermaid-svg-lhgbKdCwloHyxOfy .section–1 path,#mermaid-svg-lhgbKdCwloHyxOfy .section–1 circle,#mermaid-svg-lhgbKdCwloHyxOfy .section–1 polygon,#mermaid-svg-lhgbKdCwloHyxOfy .section–1 path{fill:hsl(240, 100%, 76.2745098039%);}#mermaid-svg-lhgbKdCwloHyxOfy .section–1 text{fill:#ffffff;}#mermaid-svg-lhgbKdCwloHyxOfy .node-icon–1{font-size:40px;color:#ffffff;}#mermaid-svg-lhgbKdCwloHyxOfy .section-edge–1{stroke:hsl(240, 100%, 76.2745098039%);}#mermaid-svg-lhgbKdCwloHyxOfy .edge-depth–1{stroke-width:17;}#mermaid-svg-lhgbKdCwloHyxOfy .section–1 line{stroke:hsl(60, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-lhgbKdCwloHyxOfy .disabled,#mermaid-svg-lhgbKdCwloHyxOfy .disabled circle,#mermaid-svg-lhgbKdCwloHyxOfy .disabled text{fill:lightgray;}#mermaid-svg-lhgbKdCwloHyxOfy .disabled text{fill:#efefef;}#mermaid-svg-lhgbKdCwloHyxOfy .section-0 rect,#mermaid-svg-lhgbKdCwloHyxOfy .section-0 path,#mermaid-svg-lhgbKdCwloHyxOfy .section-0 circle,#mermaid-svg-lhgbKdCwloHyxOfy .section-0 polygon,#mermaid-svg-lhgbKdCwloHyxOfy .section-0 path{fill:hsl(60, 100%, 73.5294117647%);}#mermaid-svg-lhgbKdCwloHyxOfy .section-0 text{fill:black;}#mermaid-svg-lhgbKdCwloHyxOfy .node-icon-0{font-size:40px;color:black;}#mermaid-svg-lhgbKdCwloHyxOfy .section-edge-0{stroke:hsl(60, 100%, 73.5294117647%);}#mermaid-svg-lhgbKdCwloHyxOfy .edge-depth-0{stroke-width:14;}#mermaid-svg-lhgbKdCwloHyxOfy .section-0 line{stroke:hsl(240, 100%, 83.5294117647%);stroke-width:3;}#mermaid-svg-lhgbKdCwloHyxOfy .disabled,#mermaid-svg-lhgbKdCwloHyxOfy .disabled circle,#mermaid-svg-lhgbKdCwloHyxOfy .disabled text{fill:lightgray;}#mermaid-svg-lhgbKdCwloHyxOfy .disabled text{fill:#efefef;}#mermaid-svg-lhgbKdCwloHyxOfy .section-1 rect,#mermaid-svg-lhgbKdCwloHyxOfy .section-1 path,#mermaid-svg-lhgbKdCwloHyxOfy .section-1 circle,#mermaid-svg-lhgbKdCwloHyxOfy .section-1 polygon,#mermaid-svg-lhgbKdCwloHyxOfy .section-1 path{fill:hsl(80, 100%, 76.2745098039%);}#mermaid-svg-lhgbKdCwloHyxOfy .section-1 text{fill:black;}#mermaid-svg-lhgbKdCwloHyxOfy .node-icon-1{font-size:40px;color:black;}#mermaid-svg-lhgbKdCwloHyxOfy .section-edge-1{stroke:hsl(80, 100%, 76.2745098039%);}#mermaid-svg-lhgbKdCwloHyxOfy .edge-depth-1{stroke-width:11;}#mermaid-svg-lhgbKdCwloHyxOfy .section-1 line{stroke:hsl(260, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-lhgbKdCwloHyxOfy .disabled,#mermaid-svg-lhgbKdCwloHyxOfy .disabled circle,#mermaid-svg-lhgbKdCwloHyxOfy .disabled text{fill:lightgray;}#mermaid-svg-lhgbKdCwloHyxOfy .disabled text{fill:#efefef;}#mermaid-svg-lhgbKdCwloHyxOfy .section-2 rect,#mermaid-svg-lhgbKdCwloHyxOfy .section-2 path,#mermaid-svg-lhgbKdCwloHyxOfy .section-2 circle,#mermaid-svg-lhgbKdCwloHyxOfy .section-2 polygon,#mermaid-svg-lhgbKdCwloHyxOfy .section-2 path{fill:hsl(270, 100%, 76.2745098039%);}#mermaid-svg-lhgbKdCwloHyxOfy .section-2 text{fill:#ffffff;}#mermaid-svg-lhgbKdCwloHyxOfy .node-icon-2{font-size:40px;color:#ffffff;}#mermaid-svg-lhgbKdCwloHyxOfy .section-edge-2{stroke:hsl(270, 100%, 76.2745098039%);}#mermaid-svg-lhgbKdCwloHyxOfy .edge-depth-2{stroke-width:8;}#mermaid-svg-lhgbKdCwloHyxOfy .section-2 line{stroke:hsl(90, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-lhgbKdCwloHyxOfy .disabled,#mermaid-svg-lhgbKdCwloHyxOfy .disabled circle,#mermaid-svg-lhgbKdCwloHyxOfy .disabled text{fill:lightgray;}#mermaid-svg-lhgbKdCwloHyxOfy .disabled text{fill:#efefef;}#mermaid-svg-lhgbKdCwloHyxOfy .section-3 rect,#mermaid-svg-lhgbKdCwloHyxOfy .section-3 path,#mermaid-svg-lhgbKdCwloHyxOfy .section-3 circle,#mermaid-svg-lhgbKdCwloHyxOfy .section-3 polygon,#mermaid-svg-lhgbKdCwloHyxOfy .section-3 path{fill:hsl(300, 100%, 76.2745098039%);}#mermaid-svg-lhgbKdCwloHyxOfy .section-3 text{fill:black;}#mermaid-svg-lhgbKdCwloHyxOfy .node-icon-3{font-size:40px;color:black;}#mermaid-svg-lhgbKdCwloHyxOfy .section-edge-3{stroke:hsl(300, 100%, 76.2745098039%);}#mermaid-svg-lhgbKdCwloHyxOfy .edge-depth-3{stroke-width:5;}#mermaid-svg-lhgbKdCwloHyxOfy .section-3 line{stroke:hsl(120, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-lhgbKdCwloHyxOfy .disabled,#mermaid-svg-lhgbKdCwloHyxOfy .disabled circle,#mermaid-svg-lhgbKdCwloHyxOfy .disabled text{fill:lightgray;}#mermaid-svg-lhgbKdCwloHyxOfy .disabled text{fill:#efefef;}#mermaid-svg-lhgbKdCwloHyxOfy .section-4 rect,#mermaid-svg-lhgbKdCwloHyxOfy .section-4 path,#mermaid-svg-lhgbKdCwloHyxOfy .section-4 circle,#mermaid-svg-lhgbKdCwloHyxOfy .section-4 polygon,#mermaid-svg-lhgbKdCwloHyxOfy .section-4 path{fill:hsl(330, 100%, 76.2745098039%);}#mermaid-svg-lhgbKdCwloHyxOfy .section-4 text{fill:black;}#mermaid-svg-lhgbKdCwloHyxOfy .node-icon-4{font-size:40px;color:black;}#mermaid-svg-lhgbKdCwloHyxOfy .section-edge-4{stroke:hsl(330, 100%, 76.2745098039%);}#mermaid-svg-lhgbKdCwloHyxOfy .edge-depth-4{stroke-width:2;}#mermaid-svg-lhgbKdCwloHyxOfy .section-4 line{stroke:hsl(150, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-lhgbKdCwloHyxOfy .disabled,#mermaid-svg-lhgbKdCwloHyxOfy .disabled circle,#mermaid-svg-lhgbKdCwloHyxOfy .disabled text{fill:lightgray;}#mermaid-svg-lhgbKdCwloHyxOfy .disabled text{fill:#efefef;}#mermaid-svg-lhgbKdCwloHyxOfy .section-5 rect,#mermaid-svg-lhgbKdCwloHyxOfy .section-5 path,#mermaid-svg-lhgbKdCwloHyxOfy .section-5 circle,#mermaid-svg-lhgbKdCwloHyxOfy .section-5 polygon,#mermaid-svg-lhgbKdCwloHyxOfy .section-5 path{fill:hsl(0, 100%, 76.2745098039%);}#mermaid-svg-lhgbKdCwloHyxOfy .section-5 text{fill:black;}#mermaid-svg-lhgbKdCwloHyxOfy .node-icon-5{font-size:40px;color:black;}#mermaid-svg-lhgbKdCwloHyxOfy .section-edge-5{stroke:hsl(0, 100%, 76.2745098039%);}#mermaid-svg-lhgbKdCwloHyxOfy .edge-depth-5{stroke-width:-1;}#mermaid-svg-lhgbKdCwloHyxOfy .section-5 line{stroke:hsl(180, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-lhgbKdCwloHyxOfy .disabled,#mermaid-svg-lhgbKdCwloHyxOfy .disabled circle,#mermaid-svg-lhgbKdCwloHyxOfy .disabled text{fill:lightgray;}#mermaid-svg-lhgbKdCwloHyxOfy .disabled text{fill:#efefef;}#mermaid-svg-lhgbKdCwloHyxOfy .section-6 rect,#mermaid-svg-lhgbKdCwloHyxOfy .section-6 path,#mermaid-svg-lhgbKdCwloHyxOfy .section-6 circle,#mermaid-svg-lhgbKdCwloHyxOfy .section-6 polygon,#mermaid-svg-lhgbKdCwloHyxOfy .section-6 path{fill:hsl(30, 100%, 76.2745098039%);}#mermaid-svg-lhgbKdCwloHyxOfy .section-6 text{fill:black;}#mermaid-svg-lhgbKdCwloHyxOfy .node-icon-6{font-size:40px;color:black;}#mermaid-svg-lhgbKdCwloHyxOfy .section-edge-6{stroke:hsl(30, 100%, 76.2745098039%);}#mermaid-svg-lhgbKdCwloHyxOfy .edge-depth-6{stroke-width:-4;}#mermaid-svg-lhgbKdCwloHyxOfy .section-6 line{stroke:hsl(210, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-lhgbKdCwloHyxOfy .disabled,#mermaid-svg-lhgbKdCwloHyxOfy .disabled circle,#mermaid-svg-lhgbKdCwloHyxOfy .disabled text{fill:lightgray;}#mermaid-svg-lhgbKdCwloHyxOfy .disabled text{fill:#efefef;}#mermaid-svg-lhgbKdCwloHyxOfy .section-7 rect,#mermaid-svg-lhgbKdCwloHyxOfy .section-7 path,#mermaid-svg-lhgbKdCwloHyxOfy .section-7 circle,#mermaid-svg-lhgbKdCwloHyxOfy .section-7 polygon,#mermaid-svg-lhgbKdCwloHyxOfy .section-7 path{fill:hsl(90, 100%, 76.2745098039%);}#mermaid-svg-lhgbKdCwloHyxOfy .section-7 text{fill:black;}#mermaid-svg-lhgbKdCwloHyxOfy .node-icon-7{font-size:40px;color:black;}#mermaid-svg-lhgbKdCwloHyxOfy .section-edge-7{stroke:hsl(90, 100%, 76.2745098039%);}#mermaid-svg-lhgbKdCwloHyxOfy .edge-depth-7{stroke-width:-7;}#mermaid-svg-lhgbKdCwloHyxOfy .section-7 line{stroke:hsl(270, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-lhgbKdCwloHyxOfy .disabled,#mermaid-svg-lhgbKdCwloHyxOfy .disabled circle,#mermaid-svg-lhgbKdCwloHyxOfy .disabled text{fill:lightgray;}#mermaid-svg-lhgbKdCwloHyxOfy .disabled text{fill:#efefef;}#mermaid-svg-lhgbKdCwloHyxOfy .section-8 rect,#mermaid-svg-lhgbKdCwloHyxOfy .section-8 path,#mermaid-svg-lhgbKdCwloHyxOfy .section-8 circle,#mermaid-svg-lhgbKdCwloHyxOfy .section-8 polygon,#mermaid-svg-lhgbKdCwloHyxOfy .section-8 path{fill:hsl(150, 100%, 76.2745098039%);}#mermaid-svg-lhgbKdCwloHyxOfy .section-8 text{fill:black;}#mermaid-svg-lhgbKdCwloHyxOfy .node-icon-8{font-size:40px;color:black;}#mermaid-svg-lhgbKdCwloHyxOfy .section-edge-8{stroke:hsl(150, 100%, 76.2745098039%);}#mermaid-svg-lhgbKdCwloHyxOfy .edge-depth-8{stroke-width:-10;}#mermaid-svg-lhgbKdCwloHyxOfy .section-8 line{stroke:hsl(330, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-lhgbKdCwloHyxOfy .disabled,#mermaid-svg-lhgbKdCwloHyxOfy .disabled circle,#mermaid-svg-lhgbKdCwloHyxOfy .disabled text{fill:lightgray;}#mermaid-svg-lhgbKdCwloHyxOfy .disabled text{fill:#efefef;}#mermaid-svg-lhgbKdCwloHyxOfy .section-9 rect,#mermaid-svg-lhgbKdCwloHyxOfy .section-9 path,#mermaid-svg-lhgbKdCwloHyxOfy .section-9 circle,#mermaid-svg-lhgbKdCwloHyxOfy .section-9 polygon,#mermaid-svg-lhgbKdCwloHyxOfy .section-9 path{fill:hsl(180, 100%, 76.2745098039%);}#mermaid-svg-lhgbKdCwloHyxOfy .section-9 text{fill:black;}#mermaid-svg-lhgbKdCwloHyxOfy .node-icon-9{font-size:40px;color:black;}#mermaid-svg-lhgbKdCwloHyxOfy .section-edge-9{stroke:hsl(180, 100%, 76.2745098039%);}#mermaid-svg-lhgbKdCwloHyxOfy .edge-depth-9{stroke-width:-13;}#mermaid-svg-lhgbKdCwloHyxOfy .section-9 line{stroke:hsl(0, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-lhgbKdCwloHyxOfy .disabled,#mermaid-svg-lhgbKdCwloHyxOfy .disabled circle,#mermaid-svg-lhgbKdCwloHyxOfy .disabled text{fill:lightgray;}#mermaid-svg-lhgbKdCwloHyxOfy .disabled text{fill:#efefef;}#mermaid-svg-lhgbKdCwloHyxOfy .section-10 rect,#mermaid-svg-lhgbKdCwloHyxOfy .section-10 path,#mermaid-svg-lhgbKdCwloHyxOfy .section-10 circle,#mermaid-svg-lhgbKdCwloHyxOfy .section-10 polygon,#mermaid-svg-lhgbKdCwloHyxOfy .section-10 path{fill:hsl(210, 100%, 76.2745098039%);}#mermaid-svg-lhgbKdCwloHyxOfy .section-10 text{fill:black;}#mermaid-svg-lhgbKdCwloHyxOfy .node-icon-10{font-size:40px;color:black;}#mermaid-svg-lhgbKdCwloHyxOfy .section-edge-10{stroke:hsl(210, 100%, 76.2745098039%);}#mermaid-svg-lhgbKdCwloHyxOfy .edge-depth-10{stroke-width:-16;}#mermaid-svg-lhgbKdCwloHyxOfy .section-10 line{stroke:hsl(30, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-lhgbKdCwloHyxOfy .disabled,#mermaid-svg-lhgbKdCwloHyxOfy .disabled circle,#mermaid-svg-lhgbKdCwloHyxOfy .disabled text{fill:lightgray;}#mermaid-svg-lhgbKdCwloHyxOfy .disabled text{fill:#efefef;}#mermaid-svg-lhgbKdCwloHyxOfy .section-root rect,#mermaid-svg-lhgbKdCwloHyxOfy .section-root path,#mermaid-svg-lhgbKdCwloHyxOfy .section-root circle,#mermaid-svg-lhgbKdCwloHyxOfy .section-root polygon{fill:hsl(240, 100%, 46.2745098039%);}#mermaid-svg-lhgbKdCwloHyxOfy .section-root text{fill:#ffffff;}#mermaid-svg-lhgbKdCwloHyxOfy .section-root span{color:#ffffff;}#mermaid-svg-lhgbKdCwloHyxOfy .section-2 span{color:#ffffff;}#mermaid-svg-lhgbKdCwloHyxOfy .icon-container{height:100%;display:flex;justify-content:center;align-items:center;}#mermaid-svg-lhgbKdCwloHyxOfy .edge{fill:none;}#mermaid-svg-lhgbKdCwloHyxOfy .mindmap-node-label{dy:1em;alignment-baseline:middle;text-anchor:middle;dominant-baseline:middle;text-align:center;}#mermaid-svg-lhgbKdCwloHyxOfy :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

有效的括号

原理

使用栈模拟匹配过程

左括号入栈

右括号检查栈顶是否匹配

方法

顺序遍历字符串

匹配时出栈

最后检查栈是否为空

分析

时间复杂度 O(n)

空间复杂度 O(n)

五、算法流程图

#mermaid-svg-NtHh7qDoRc3EbpUH{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-NtHh7qDoRc3EbpUH .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-NtHh7qDoRc3EbpUH .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-NtHh7qDoRc3EbpUH .error-icon{fill:#552222;}#mermaid-svg-NtHh7qDoRc3EbpUH .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-NtHh7qDoRc3EbpUH .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-NtHh7qDoRc3EbpUH .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-NtHh7qDoRc3EbpUH .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-NtHh7qDoRc3EbpUH .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-NtHh7qDoRc3EbpUH .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-NtHh7qDoRc3EbpUH .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-NtHh7qDoRc3EbpUH .marker{fill:#333333;stroke:#333333;}#mermaid-svg-NtHh7qDoRc3EbpUH .marker.cross{stroke:#333333;}#mermaid-svg-NtHh7qDoRc3EbpUH svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-NtHh7qDoRc3EbpUH p{margin:0;}#mermaid-svg-NtHh7qDoRc3EbpUH .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-NtHh7qDoRc3EbpUH .cluster-label text{fill:#333;}#mermaid-svg-NtHh7qDoRc3EbpUH .cluster-label span{color:#333;}#mermaid-svg-NtHh7qDoRc3EbpUH .cluster-label span p{background-color:transparent;}#mermaid-svg-NtHh7qDoRc3EbpUH .label text,#mermaid-svg-NtHh7qDoRc3EbpUH span{fill:#333;color:#333;}#mermaid-svg-NtHh7qDoRc3EbpUH .node rect,#mermaid-svg-NtHh7qDoRc3EbpUH .node circle,#mermaid-svg-NtHh7qDoRc3EbpUH .node ellipse,#mermaid-svg-NtHh7qDoRc3EbpUH .node polygon,#mermaid-svg-NtHh7qDoRc3EbpUH .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-NtHh7qDoRc3EbpUH .rough-node .label text,#mermaid-svg-NtHh7qDoRc3EbpUH .node .label text,#mermaid-svg-NtHh7qDoRc3EbpUH .image-shape .label,#mermaid-svg-NtHh7qDoRc3EbpUH .icon-shape .label{text-anchor:middle;}#mermaid-svg-NtHh7qDoRc3EbpUH .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-NtHh7qDoRc3EbpUH .rough-node .label,#mermaid-svg-NtHh7qDoRc3EbpUH .node .label,#mermaid-svg-NtHh7qDoRc3EbpUH .image-shape .label,#mermaid-svg-NtHh7qDoRc3EbpUH .icon-shape .label{text-align:center;}#mermaid-svg-NtHh7qDoRc3EbpUH .node.clickable{cursor:pointer;}#mermaid-svg-NtHh7qDoRc3EbpUH .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-NtHh7qDoRc3EbpUH .arrowheadPath{fill:#333333;}#mermaid-svg-NtHh7qDoRc3EbpUH .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-NtHh7qDoRc3EbpUH .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-NtHh7qDoRc3EbpUH .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-NtHh7qDoRc3EbpUH .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-NtHh7qDoRc3EbpUH .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-NtHh7qDoRc3EbpUH .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-NtHh7qDoRc3EbpUH .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-NtHh7qDoRc3EbpUH .cluster text{fill:#333;}#mermaid-svg-NtHh7qDoRc3EbpUH .cluster span{color:#333;}#mermaid-svg-NtHh7qDoRc3EbpUH div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-NtHh7qDoRc3EbpUH .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-NtHh7qDoRc3EbpUH rect.text{fill:none;stroke-width:0;}#mermaid-svg-NtHh7qDoRc3EbpUH .icon-shape,#mermaid-svg-NtHh7qDoRc3EbpUH .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-NtHh7qDoRc3EbpUH .icon-shape p,#mermaid-svg-NtHh7qDoRc3EbpUH .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-NtHh7qDoRc3EbpUH .icon-shape rect,#mermaid-svg-NtHh7qDoRc3EbpUH .image-shape rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-NtHh7qDoRc3EbpUH .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-NtHh7qDoRc3EbpUH .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-NtHh7qDoRc3EbpUH :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

是

否

是

否

是

否

是

否

栈为空

栈不为空

开始

字符串为空?

返回 true

创建空栈

遍历字符串每个字符

当前字符是左括号?

入栈

栈是否为空?

返回 false

栈顶与当前括号是否匹配?

出栈

继续遍历

遍历结束

返回 true

返回 false

六、详细步骤解析

七、Java 代码实现

import java.util.Stack;

public class ValidParentheses {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();

for (char ch : s.toCharArray()) {
// 左括号入栈
if (ch == '(' || ch == '{' || ch == '[') {
stack.push(ch);
} else {
// 如果右括号出现但栈为空
if (stack.isEmpty()) {
return false;
}
char top = stack.pop();
// 判断是否匹配
if ((ch == ')' && top != '(') ||
(ch == '}' && top != '{') ||
(ch == ']' && top != '[')) {
return false;
}
}
}

// 栈空则有效，否则无效
return stack.isEmpty();
}
}

八、复杂度分析