{"id":191,"date":"2022-01-07T09:32:44","date_gmt":"2022-01-07T01:32:44","guid":{"rendered":"https:\/\/www.wennroy.com\/?p=191"},"modified":"2022-01-07T09:33:07","modified_gmt":"2022-01-07T01:33:07","slug":"1614-maximum-nesting-depth-of-the-parentheses","status":"publish","type":"post","link":"https:\/\/wennroy.com\/index.php\/2022\/01\/07\/1614-maximum-nesting-depth-of-the-parentheses\/","title":{"rendered":"1614. \u62ec\u53f7\u7684\u6700\u5927\u5d4c\u5957\u6df1\u5ea6"},"content":{"rendered":"\n

\u5982\u679c\u5b57\u7b26\u4e32\u6ee1\u8db3\u4ee5\u4e0b\u6761\u4ef6\u4e4b\u4e00\uff0c\u5219\u53ef\u4ee5\u79f0\u4e4b\u4e3a \u6709\u6548\u62ec\u53f7\u5b57\u7b26\u4e32\uff08valid parentheses string\uff0c\u53ef\u4ee5\u7b80\u5199\u4e3a VPS\uff09\uff1a<\/p>\n\n\n\n

\u5b57\u7b26\u4e32\u662f\u4e00\u4e2a\u7a7a\u5b57\u7b26\u4e32 “”\uff0c\u6216\u8005\u662f\u4e00\u4e2a\u4e0d\u4e3a “(” \u6216 “)” \u7684\u5355\u5b57\u7b26\u3002
\u5b57\u7b26\u4e32\u53ef\u4ee5\u5199\u4e3a AB\uff08A \u4e0e B \u5b57\u7b26\u4e32\u8fde\u63a5\uff09\uff0c\u5176\u4e2d A \u548c B \u90fd\u662f \u6709\u6548\u62ec\u53f7\u5b57\u7b26\u4e32 \u3002
\u5b57\u7b26\u4e32\u53ef\u4ee5\u5199\u4e3a (A)\uff0c\u5176\u4e2d A \u662f\u4e00\u4e2a \u6709\u6548\u62ec\u53f7\u5b57\u7b26\u4e32 \u3002
\u7c7b\u4f3c\u5730\uff0c\u53ef\u4ee5\u5b9a\u4e49\u4efb\u4f55\u6709\u6548\u62ec\u53f7\u5b57\u7b26\u4e32 S \u7684 \u5d4c\u5957\u6df1\u5ea6 depth(S)\uff1a<\/p>\n\n\n\n

depth(“”) = 0
depth(C) = 0\uff0c\u5176\u4e2d C \u662f\u5355\u4e2a\u5b57\u7b26\u7684\u5b57\u7b26\u4e32\uff0c\u4e14\u8be5\u5b57\u7b26\u4e0d\u662f “(” \u6216\u8005 “)”
depth(A + B) = max(depth(A), depth(B))\uff0c\u5176\u4e2d A \u548c B \u90fd\u662f \u6709\u6548\u62ec\u53f7\u5b57\u7b26\u4e32
depth(“(” + A + “)”) = 1 + depth(A)\uff0c\u5176\u4e2d A \u662f\u4e00\u4e2a \u6709\u6548\u62ec\u53f7\u5b57\u7b26\u4e32
\u4f8b\u5982\uff1a””\u3001”()()”\u3001”()(()())” \u90fd\u662f \u6709\u6548\u62ec\u53f7\u5b57\u7b26\u4e32\uff08\u5d4c\u5957\u6df1\u5ea6\u5206\u522b\u4e3a 0\u30011\u30012\uff09\uff0c\u800c “)(” \u3001”(()” \u90fd\u4e0d\u662f \u6709\u6548\u62ec\u53f7\u5b57\u7b26\u4e32 \u3002<\/p>\n\n\n\n

\u7ed9\u4f60\u4e00\u4e2a \u6709\u6548\u62ec\u53f7\u5b57\u7b26\u4e32 s\uff0c\u8fd4\u56de\u8be5\u5b57\u7b26\u4e32\u7684 s \u5d4c\u5957\u6df1\u5ea6 \u3002<\/p>\n\n\n\n

\u5bf9\u4e8e\u8fd9\u79cd\u95ee\u9898\u6808\u627e\u62ec\u53f7\u5373\u53ef\uff0c\u90a3\u4e48\u4ee3\u78013\u5206\u949f\u5c31\u80fd\u5199\u5b8c\uff0c<\/p>\n\n\n\n

class Solution:\n    def maxDepth(self, s: str) -> int:\n        if len(s) <= 1:\n            return 0\n        stack = []\n        max_len = 0\n        for cha in s:\n            if cha == \"(\":\n                stack.append(\"(\")\n                if len(stack)>max_len:\n                    max_len = len(stack)\n            elif cha == \")\":\n                stack.pop()\n        return max_len\n<\/pre>\n\n\n\n
\u5b98\u65b9\u6807\u7b54\uff1a<\/p>\n\n\n\n
class Solution:\n    def maxDepth(self, s: str) -> int:\n        ans, size = 0, 0\n        for ch in s:\n            if ch == '(':\n                size += 1\n                ans = max(ans, size)\n            elif ch == ')':\n                size -= 1\n        return ans<\/pre>\n\n\n\n
\u601d\u8def\u57fa\u672c\u4e00\u81f4\u3002<\/p>\n\n\n\n
\u6765\u6e90\uff1a\u529b\u6263\uff08LeetCode\uff09
\u94fe\u63a5\uff1ahttps:\/\/leetcode-cn.com\/problems\/maximum-nesting-depth-of-the-parentheses
\u8457\u4f5c\u6743\u5f52\u9886\u6263\u7f51\u7edc\u6240\u6709\u3002\u5546\u4e1a\u8f6c\u8f7d\u8bf7\u8054\u7cfb\u5b98\u65b9\u6388\u6743\uff0c\u975e\u5546\u4e1a\u8f6c\u8f7d\u8bf7\u6ce8\u660e\u51fa\u5904\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"
\u5982\u679c\u5b57\u7b26\u4e32\u6ee1\u8db3\u4ee5\u4e0b\u6761\u4ef6\u4e4b\u4e00\uff0c\u5219\u53ef\u4ee5\u79f0\u4e4b\u4e3a \u6709\u6548\u62ec\u53f7 …<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_import_markdown_pro_load_document_selector":0,"_import_markdown_pro_submit_text_textarea":"","footnotes":""},"categories":[6,11,12],"tags":[],"class_list":["post-191","post","type-post","status-publish","format-standard","hentry","category-leetcode","category-strings","category-stack-simulation"],"_links":{"self":[{"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/posts\/191","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/comments?post=191"}],"version-history":[{"count":1,"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/posts\/191\/revisions"}],"predecessor-version":[{"id":192,"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/posts\/191\/revisions\/192"}],"wp:attachment":[{"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/media?parent=191"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/categories?post=191"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wennroy.com\/index.php\/wp-json\/wp\/v2\/tags?post=191"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}