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"()()"
最长有效括号。题意是给一个字符串，返回其中能构成的最长的有效括号的长度。
这个题可以用动态规划做，但是不是很容易理解，我这里给出一个栈的解法。首先创建一个stack，然后创建一个start变量，暂时记为-1。记为-1的原因是有可能input从第一个字符（index = 0）开始就是有效的括号对，所以需要记成-1。接着开始遍历input
时间O(n)
空间O(n)
Java实现
1 class Solution { 2 public int longestValidParentheses(String s) { 3 // corner case 4 if (s == null || s.length() == 0) { 5 return 0; 6 } 7 8 // normal case 9 Stack<Integer> stack = new Stack<>(); 10 int res = 0; 11 int start = -1; 12 for (int i = 0; i < s.length(); i++) { 13 if (s.charAt(i) == ‘(‘) { 14 stack.push(i); 15 } else { 16 if (stack.isEmpty()) { 17 start = i; 18 } else { 19 stack.pop(); 20 if (stack.isEmpty()) { 21 res = Math.max(res, i - start); 22 } else { 23 res = Math.max(res, i - stack.peek()); 24 } 25 } 26 } 27 } 28 return res; 29 } 30 }
JavaScript实现
1 /** 2 * @param {string} s 3 * @return {number} 4 */ 5 var longestValidParentheses = function(s) { 6 // corner case 7 if (s === null || s.length === 0) { 8 return 0; 9 } 10 11 // normal case 12 let start = -1; 13 let res = 0; 14 let stack = []; 15 for (let i = 0; i < s.length; i++) { 16 if (s.charAt(i) == ‘(‘) { 17 stack.push(i); 18 } else { 19 if (stack.length === 0) { 20 start = i; 21 } else { 22 stack.pop(); 23 if (stack.length === 0) { 24 res = Math.max(res, i - start); 25 } else { 26 res = Math.max(res, i - stack[stack.length - 1]); 27 } 28 } 29 } 30 } 31 return res; 32 };
[LeetCode] 32. Longest Valid Parentheses
原文：https://www.cnblogs.com/cnoodle/p/13233582.html