{"id":4151,"date":"2018-10-03T09:07:40","date_gmt":"2018-10-03T16:07:40","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4151"},"modified":"2018-10-03T19:15:46","modified_gmt":"2018-10-04T02:15:46","slug":"leetcode-32-longest-valid-parentheses","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/stack\/leetcode-32-longest-valid-parentheses\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 32. Longest Valid Parentheses"},"content":{"rendered":"

Problem<\/strong><\/h1>\n

Given a string containing just the characters\u00a0'('<\/code>\u00a0and\u00a0')'<\/code>, find the length of the longest valid (well-formed) parentheses substring.<\/p>\n

Example 1:<\/strong><\/p>\n

Input:<\/strong> \"(()\"\r\nOutput:<\/strong> 2\r\nExplanation:<\/strong> The longest valid parentheses substring is \"()\"<\/code><\/pre>\n
Example 2:<\/strong><\/p>\n
Input:<\/strong> \")()())<\/code>\" Output:<\/strong> 4 Explanation:<\/strong> The longest valid parentheses substring is \"()()\"<\/code><\/pre>\n
Solution: Stack<\/strong><\/h1>\n
Use a stack to track the index of all unmatched open parentheses.<\/p>\n
Time complexity: O(n)<\/p>\n
Space complexity: O(n)<\/p>\n
\n
C++<\/h2>\n
\n\n
\/\/ Author: Huahua\r\nclass Solution {\r\npublic:\r\n  int longestValidParentheses(string s) {\r\n    stack<int> q;\r\n    int start = 0;\r\n    int ans = 0;\r\n    for (int i = 0;i < s.length(); i++) {\r\n      if(s[i] == '(') {\r\n        q.push(i);\r\n      } else {\r\n        if (q.empty()) {\r\n          start = i + 1;\r\n        } else {\r\n          int index = q.top(); q.pop();\r\n          ans = max(ans, q.empty() ? i - start + 1 : i - q.top());          \r\n        }\r\n      }\r\n    }\r\n    return ans;\r\n  }\r\n};<\/pre>\n\n<\/div>
Python3<\/h2>\n
\n\n
# Author: Huahua\r\nclass Solution:\r\n  def longestValidParentheses(self, s):\r\n    q = []\r\n    start, ans = 0, 0\r\n    for i in range(len(s)):\r\n      if s[i] == '(':\r\n        q.append(i)\r\n        continue\r\n      if not q: \r\n        start = i + 1\r\n      else:\r\n        q.pop()\r\n        ans = max(ans, i - q[-1] if q else i - start + 1)\r\n    return ans<\/pre>\n
 <\/p>\n<\/div><\/div>\n
Related Problems<\/strong><\/h1>\n