1"use strict";(self.webpackChunkcode_fictionist=self.webpackChunkcode_fictionist||[]).push([[977],{28453:(e,n,t)=>{t.d(n,{R:()=>i,x:()=>a});var s=t(96540);const r={},c=s.createContext(r);function i(e){const n=s.useContext(c);return s.useMemo((function(){return"function"==typeof e?e(n):{...n,...e}}),[n,e])}function a(e){let n;return n=e.disableParentContext?"function"==typeof e.components?e.components(r):e.components||r:i(e.components),s.createElement(c.Provider,{value:n},e.children)}},39793:(e,n,t)=>{t.r(n),t.d(n,{assets:()=>o,contentTitle:()=>a,default:()=>h,frontMatter:()=>i,metadata:()=>s,toc:()=>l});const s=JSON.parse('{"id":"notes/Algorithm/LeetCode/Stack","title":"[Stack] 20. Valid Parentheses","description":"Leetcode 20. Valid Parentheses","source":"@site/docs/notes/Algorithm/LeetCode/20-Stack.mdx","sourceDirName":"notes/Algorithm/LeetCode","slug":"/notes/Algorithm/LeetCode/Stack","permalink":"/docs/notes/Algorithm/LeetCode/Stack","draft":false,"unlisted":false,"tags":[{"inline":true,"label":"leetcode","permalink":"/docs/tags/leetcode"},{"inline":true,"label":"stack","permalink":"/docs/tags/stack"}],"version":"current","lastUpdatedAt":1767358364000,"sidebarPosition":20,"frontMatter":{"title":"[Stack] 20. Valid Parentheses","tags":["leetcode","stack"],"keywords":["LeetCode","Stack","Valid Parentheses"]},"sidebar":"notes","previous":{"title":"LeetCode","permalink":"/docs/category/leetcode"},"next":{"title":"[Array] 26. Remove Duplicates from Sorted Array","permalink":"/docs/notes/Algorithm/LeetCode/Array"}}');var r=t(74848),c=t(28453);const i={title:"[Stack] 20. Valid Parentheses",tags:["leetcode","stack"],keywords:["LeetCode","Stack","Valid Parentheses"]},a=void 0,o={},l=[{value:"\u984c\u76ee\u8981\u6c42",id:"\u984c\u76ee\u8981\u6c42",level:2},{value:"\u89e3\u984c\u601d\u8def",id:"\u89e3\u984c\u601d\u8def",level:2}];function d(e){const n={a:"a",admonition:"admonition",br:"br",code:"code",h2:"h2",li:"li",ol:"ol",p:"p",pre:"pre",ul:"ul",...(0,c.R)(),...e.components};return(0,r.jsxs)(r.Fragment,{children:[(0,r.jsx)(n.admonition,{type:"info",children:(0,r.jsx)(n.p,{children:(0,r.jsx)(n.a,{href:"https://leetcode.com/problems/valid-parentheses/description/",children:"Leetcode 20. Valid Parentheses"})})}),"\n",(0,r.jsx)(n.h2,{id:"\u984c\u76ee\u8981\u6c42",children:"\u984c\u76ee\u8981\u6c42"}),"\n",(0,r.jsxs)(n.p,{children:["Given a string s containing just the characters ",(0,r.jsx)(n.code,{children:"'('"}),", ",(0,r.jsx)(n.code,{children:"')'"}),", ",(0,r.jsx)(n.code,{children:"'{'"}),", ",(0,r.jsx)(n.code,{children:"'}'"}),", ",(0,r.jsx)(n.code,{children:"'['"})," and ",(0,r.jsx)(n.code,{children:"']'"}),", determine if the input string is valid.",(0,r.jsx)(n.br,{}),"\n","An input string is valid if:"]}),"\n",(0,r.jsxs)(n.ol,{children:["\n",(0,r.jsx)(n.li,{children:"Open brackets must be closed by the same type of brackets."}),"\n",(0,r.jsx)(n.li,{children:"Open brackets must be closed in the correct order."}),"\n",(0,r.jsx)(n.li,{children:"Every close bracket has a corresponding open bracket of the same type."}),"\n"]}),"\n",(0,r.jsx)(n.p,{children:"Expected input and output:"}),"\n",(0,r.jsx)(n.pre,{children:(0,r.jsx)(n.code,{children:'Input: s = "()"\nOutput: true\n\nInput: s = "()[]{}"\nOutput: true\n\nInput: s = "(]"\nOutput: false\n\nInput: s = "([])"\nOutput: true\n\nInput: s = "([)]"\nOutput: false\n'})}),"\n",(0,r.jsx)(n.h2,{id:"\u89e3\u984c\u601d\u8def",children:"\u89e3\u984c\u601d\u8def"}),"\n",(0,r.jsxs)(n.p,{children:["\u672c\u984c\u662f\u5f88\u7d93\u5178\u7684 stack \u984c\u76ee\uff0c\u975e\u5e38\u9069\u5408\u5229\u7528\u5176 LIFO (Last In, First Out) \u7684\u7279\u6027\u4f86\u89e3\u6c7a\u3002",(0,r.jsx)(n.br,{}),"\n","\u9019\u984c\u7684\u89e3\u984c\u601d\u8def\u5728\u65bc\u638c\u63e1\u5169\u500b\u539f\u5247\uff1a"]}),"\n",(0,r.jsxs)(n.ol,{children:["\n",(0,r.jsx)(n.li,{children:"\u6bcf\u500b\u5de6\u62ec\u865f\u5fc5\u6709\u4e00\u500b\u5c0d\u61c9\u7684\u53f3\u62ec\u865f\u3002"}),"\n",(0,r.jsx)(n.li,{children:"\u4e00\u7d44\u62ec\u865f\u5167\u82e5\u6709\u5176\u4ed6\u62ec\u865f\uff0c\u5167\u90e8\u7684\u62ec\u865f\u5fc5\u9808\u4e5f\u5148\u914d\u5c0d\u5b8c\u6210 (\u9589\u5408)\u3002"}),"\n"]}
1),"\n",(0,r.jsxs)(n.p,{children:["\u6eff\u8db3\u9019\u5169\u9805\u539f\u5247\uff0c\u90a3 method \u5c31\u6703 return true\uff0c\u5224\u5b9a\u5176\u70ba\u6709\u6548\u7684\u62ec\u865f\u7d44\u5408\u3002",(0,r.jsx)(n.br,{}),"\n","\u53cd\u4e4b\uff0c\u82e5\u6709\u4efb\u4f55\u4e00\u9805\u4e0d\u7b26\u5408\uff0cmethod \u5c31\u6703 return false\u3002"]}),"\n",(0,r.jsxs)(n.p,{children:["\u90a3\u70ba\u4f55\u8aaa stack \u662f\u9019\u984c\u7684\u6700\u4f73\u89e3\u6cd5\u5462\uff1f",(0,r.jsx)(n.br,{}),"\n","\u539f\u56e0\u5728\u65bc LIFO \u7684\u7279\u6027\u975e\u5e38\u9069\u5408\u7528\u4f86\u6aa2\u67e5\u4e0a\u8ff0\u5169\u500b\u539f\u5247\u3002",(0,r.jsx)(n.br,{}),"\n","\u6211\u5011\u53ef\u4ee5\u9019\u6a23\u505a\uff1a"]}),"\n",(0,r.jsxs)(n.ol,{children:["\n",(0,r.jsx)(n.li,{children:"\u9047\u5230\u5de6\u62ec\u865f\u6642\uff0c\u6211\u5011\u5148\u5c07\u5de6\u62ec\u865f\u7d66 push \u9032 stack \u88e1\u3002"}),"\n",(0,r.jsxs)(n.li,{children:["\u7576\u9047\u5230\u53f3\u62ec\u865f\u6642\uff0c\u6211\u5011\u6aa2\u67e5 stack \u9802\u7aef\u7684\u5143\u7d20\u662f\u5426\u70ba\u5c0d\u61c9\u7684\u5de6\u62ec\u865f\u3002","\n",(0,r.jsxs)(n.ul,{children:["\n",(0,r.jsx)(n.li,{children:"\u82e5\u662f\uff0c\u8868\u793a\u9019\u5c0d\u62ec\u865f\u662f\u6709\u6548\u7684\uff0c\u6211\u5011\u5c31\u5c07 stack \u9802\u7aef\u7684\u5de6\u62ec\u865f pop \u51fa stack\u3002"}),"\n",(0,r.jsx)(n.li,{children:"\u82e5\u4e0d\u662f\uff0c\u8868\u793a\u9019\u5c0d\u62ec\u865f\u7121\u6548\uff0c\u6211\u5011\u76f4\u63a5 return false\uff0c\u53ef\u4ee5\u76f4\u63a5\u7d42\u6b62\u7a0b\u5f0f (\u56e0\u70ba\u53ea\u8981\u4e00\u500b\u662f\u4e0d\u5408\u6cd5\uff0c\u5c31\u8a72\u56de\u50b3 false\uff0c\u5f8c\u9762\u7684\u904b\u7b97\u90fd\u7d14\u5c6c\u591a\u9918)\u3002"}),"\n"]}),"\n"]}),"\n",(0,r.jsx)(n.li,{children:"\u904d\u6b77\u5b8c\u6574\u500b\u5b57\u4e32\u5f8c\uff0c\u82e5\u5132\u5b58\u5de6\u62ec\u865f\u7684 stack \u662f\u7a7a\u7684\uff0c\u8868\u793a\u6240\u6709\u7684\u62ec\u865f\u90fd\u6210\u529f\u914d\u5c0d\uff0c\u6211\u5011\u5c31 return true\uff1b\u53cd\u4e4b\uff0c\u82e5 stack \u88e1\u9084\u6709\u5143\u7d20\uff0c\u8868\u793a\u6709\u672a\u914d\u5c0d\u7684\u5de6\u62ec\u865f\uff0c\u6211\u5011\u5c31 return false\u3002"}),"\n"]}),"\n",(0,r.jsx)(n.pre,{children:(0,r.jsx)(n.code,{className:"language-java",children:"class Solution {\n public boolean isValid(String s) {\n boolean isValid = true;\n\n char[] charArray = s.toCharArray();\n Stack<Character> stack = new Stack<>();\n\n for (char c : charArray) {\n if (c == '(' || c == '[' || c == '{') {\n stack.push(c);\n } else {\n if (stack.isEmpty()) {\n isValid = false;\n break;\n }\n\n char top = stack.pop();\n if ((c == ')' && top != '(') ||\n (c == ']' && top != '[') ||\n (c == '}' && top != '{')) {\n isValid = false;\n break;\n }\n }\n }\n\n return isValid && stack.isEmpty();\n }\n}\n"})})]})}function h(e={}){const{wrapper:n}={...(0,c.R)(),...e.components};return n?(0,r.jsx)(n,{...e,children:(0,r.jsx)(d,{...e})}):d(e)}}}]);
Line numbers count LF bytes from the start of the resource, as the search results do. Vendor segments are library code the classifier recognised; they are stored but not indexed. Bytes are shown as Latin1 characters, one per byte.