\u7ed9\u4f60\u4e00\u4e2a\u53ea\u5305\u542b ‘(‘ \u548c ‘)’ \u7684\u5b57\u7b26\u4e32\uff0c\u627e\u51fa\u6700\u957f\u6709\u6548\uff08\u683c\u5f0f\u6b63\u786e\u4e14\u8fde\u7eed\uff09\u62ec\u53f7 \u5b50\u4e32 \u7684\u957f\u5ea6\u3002
\n\u5de6\u53f3\u62ec\u53f7\u5339\u914d\uff0c\u5373\u6bcf\u4e2a\u5de6\u62ec\u53f7\u90fd\u6709\u5bf9\u5e94\u7684\u53f3\u62ec\u53f7\u5c06\u5176\u95ed\u5408\u7684\u5b57\u7b26\u4e32\u662f\u683c\u5f0f\u6b63\u786e\u7684\uff0c\u6bd4\u5982 “(()())”\u3002<\/p>\n
\u793a\u4f8b\uff1a
\n\u8f93\u5165\uff1as = “(()”
\n\u8f93\u51fa\uff1a2
\n\u89e3\u91ca\uff1a\u6700\u957f\u6709\u6548\u62ec\u53f7\u5b50\u4e32\u662f “()”<\/p>\n
\u52a8\u6001\u89c4\u5212\u3002 \u5728 dp \u4e2d\u53d6\u6700\u5927\u503c\u5373\u53ef. \u9898\u76ee\u63cf\u8ff0 \u7ed9\u4f60\u4e00\u4e2a\u53ea\u5305\u542b ‘(‘ \u548c ‘)’ \u7684\u5b57\u7b26\u4e32\uff0c\u627e\u51fa\u6700 […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[20,40],"class_list":["post-1041","post","type-post","status-publish","format-standard","hentry","category-algo","tag-leetcode","tag-40"],"_links":{"self":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/1041","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1041"}],"version-history":[{"count":1,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/1041\/revisions"}],"predecessor-version":[{"id":1042,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/1041\/revisions\/1042"}],"wp:attachment":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1041"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1041"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1041"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\n\u8bbe dp[i] \u8868\u793a\u4ee5\u4f4d\u7f6e i \u7ed3\u5c3e\u7684\u6709\u6548\u5b50\u4e32\u6700\u5927\u957f\u5ea6\uff0c\u5219\u5f53 s[i] \u4e3a ‘)’ \u65f6\uff1a
\n– s[i – 1] \u4e3a ‘(‘ \uff0c\u4f8b\u5982 “()()<\/strong>” \uff0cdp[i] = dp[i – 2] + 2
\n– s[i – 1] \u4e3a ‘)’ \u4e14 i – 1 \u5904\u4e3a\u6709\u6548\u5b50\u4e32 \u4e14 \u5b50\u4e32\u524d\u4e3a ‘(‘\uff0c\u4f8b\u5982”()(())<\/strong>“\uff0cdp[i] = dp[i – 1] + 2 + dp[\u5b50\u4e32\u524d2\u4f4d]<\/p>\n
\n\u65f6\u95f4\u590d\u6742\u5ea6 O(n)<\/p>\nJava<\/h1>\n
public int longestValidParentheses(String s) {\n int[] dp = new int[s.length()];\n int ans = 0;\n for (int i = 1; i < s.length(); i++) {\n char ch = s.charAt(i);\n char pre = s.charAt(i - 1);\n if (ch == ')') {\n if (pre == '(') {\n dp[i] = i >= 2 ? dp[i - 2] + 2 : 2;\n } else {\n int before = i - dp[i - 1] - 1;\n if (before >= 0 && s.charAt(before) == '(') {\n dp[i] = dp[i - 1] + 2;\n if (before >= 1) {\n dp[i] += dp[before - 1];\n }\n }\n }\n }\n ans = Math.max(ans, dp[i]);\n }\n return ans;\n}\n<\/code><\/pre>\nKotlin<\/h1>\n
fun longestValidParentheses(s: String): Int {\n val dp = IntArray(s.length)\n var ans = 0\n for (i in s.indices) {\n if (s[i] == ')' && i - 1 >= 0) {\n if (s[i - 1] == '(') {\n dp[i] = if (i - 2 >= 0) dp[i - 2] + 2 else 2\n } else if (dp[i - 1] > 0) {\n val before = i - dp[i - 1] - 1\n if (before >= 0 && s[before] == '(') {\n dp[i] = dp[i - 1] + 2\n if (before >= 1) {\n dp[i] += dp[before - 1]\n }\n }\n }\n }\n ans = max(ans, dp[i])\n }\n return ans\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"