Given a string containing just the characters ‘(‘ and ‘)‘, find the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"
Example 2:
Input: ")()())" Output: 4 Explanation: The longest valid parentheses substring is"()()"
1 class Solution { 2 3 public int longestValidParentheses(String s) { 4 int n = s.length(); 5 int []f = new int[n]; 6 int []stack = new int[n]; 7 int ans = 0; 8 int k = 0; 9 for (int i = 0; i < n; ++i) { 10 if (s.charAt(i) == ‘(‘) { 11 stack[k++] = i; 12 } 13 if (s.charAt(i) == ‘)‘) { 14 if (k > 0) { 15 f[i] = i - stack[k - 1] + 1; 16 if (stack[k - 1] - 1 >= 0 && f[stack[k - 1] - 1] > 0) 17 f[i] += f[stack[k - 1] - 1]; 18 k--; 19 } else { 20 k = 0; 21 22 } 23 24 } 25 } 26 for (int i = 0; i < n; ++i) { 27 ans = Math.max(ans, f[i]); 28 } 29 30 return ans; 31 } 32 }
原文：https://www.cnblogs.com/hyxsolitude/p/12309467.html