32. Longest Valid Parentheses

Tags

1. String
2. Dynamic Programming

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

题意：

给定一个字符串只包含字符'('和')'，找到最长的有效长度（形成）括号内的子串。 例如'(()'，最长有效括号子串是'()'，其长度= 2。 另一个例子是')()())'，其中最长的子串是有效的括号'()()'，其长度= 4。

分析：

由题意可知，题目是获取能完整匹配成小括号的字符串长度值。那么我们可以按照20题的思路，通过一个临时栈来协助我们求得长度值。重点就在于小括号必须成对出现。也就是说'()'的出栈入栈必须一一对应，不然就不满足要求。

思路：

1. 循环字符串中的每个字符
2. 当字符等于'('时，将字符的位置记录到栈中，否则等于')'时，则比较stack中是否有记录能与之比对，如果可以则出栈，记录长度。如果不比对，则将该位置作为新的初始位置
3. 循环执行步骤2，取满足要求结果的最大值作为最后的长度。

复杂度：

时间复杂度O(n)

Js实现：

/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function(s) {
    const stack = [];
    let max = 0;
    let left = -1;

    for(let j = 0; j < s.length; j++) {
        if(s[j] == '(') {
            stack.push(j);
        } else {
              //一一比对不成功
            if(stack.length === 0) {
                left = j;
            } else {
                stack.pop();
                // 一一对应比对成功`()()`
                if(stack.length === 0) {
                    max = Math.max(max, j - left);
                } else {
                // 嵌套情况`(())`
                    max = Math.max(max, j - stack[stack.length - 1])
                }
            } 
        }
    }
    return max;
};