一、栈方法

请仔细思考注释说的话，来模拟 (())() 运行的过程，这道题也就解决了。
/**
  * 
  * @param s string字符串 
  * @return int整型
  */
function longestValidParentheses( s ) {
    // write code here
    if(!s)    return 0;
    const n = s.length;
    let max = 0;       // 为了记录最长的格式正确的括号子串的长度，需要借助一个变量
    // 诸如其他括号匹配问题，我们都能想到用栈，但是这题题目指明了只有 '(' 和 ')'
    // 那我们又需要用这个栈做什么呢？它应该保存什么
    // 我们不可能在栈中保存 '('，那是没意义的。
    // 括号匹配问题，当碰到 ')' 时，需要依据栈来确定是否匹配
    // 而这题题目又需要的是最长的合法括号子串的长度，这就很容易让我们联想到下标
    // 那我们就拟定栈中存储的应该是 '(' 的下标
    const stack = [];  
    
    // 那么问题来了，我们栈中放的是左括号的下标，那我们可能会想着
    // 当前匹配的合法括号子串的长度是，当前下标 i - stack[stack.length - 1](栈顶元素) + 1
    // 但是这就会遇到一种情况 ()()() ，这种情况如果我们只考虑出栈的左括号的下标
    // 那当前最长合法括号子串的长度将一直保持 2 ，显然这不是如我们预期的，因为它应该是 6
    // 我们考虑这个情况的性质，可以很清楚的就能发现，只要我们记录发生匹配时的 起始位置 start
    // 我们就能依据 i - start + 1 的方式来计算 最长括号子串的长短
    // 但由这，又衍生出一种情况 (())()
    // 在这个合法的括号子串里，你会很容易想到，对嘛，直接在最后一个 ')' 发生匹配时
    // 计算 i - start + 1 就能得到解，因为我们 start 的含义是 发生匹配时的起始位置

    // 但实际上，只由 start 我们并不能确保，start - i 的子串是合法的
    // 因为 (())() 这种情况，第一次发生匹配时，是在下标 2 的位置，它与下标 1 匹配
    // 如果我们由 start 来计算值， i - start + 1，假如 start 我们给定 0 
    // 这时候 2 - 0 + 1 = 3 ？？发现了问题，怎么可能匹配长度是奇数呢，而且我的长度应该是由 下标 1 决定
    
    // 综合前面的考虑，我们需要'两'种计算最长合法括号子串的方式：

    // 1. (())
    // 这种情况的性质就是，碰到右括号时，栈中是有左括号元素的
    // 所以我们便可以得出一个条件 s[i] === ')' && stack.length 时，长度 = i - stack[stack.length - 1]
    // 这里用了个技巧 stack.length ，js 中 0 的 boolean 值是 false 所以只有在 stack.length 不为 0 时满足
    // 这种情况的解决了，我们接着解决下面这种情况
    
    // 2. ()()
    // 这种情况的性质就是，当我第一次发生匹配时我需要记录它的起始位置，并且栈中只有一个括号会匹配
    // 这样在之后每次匹配时我就能用起始位置来计算长度
    // 是的，那我们如何记录起始位置呢，是在每次发生匹配时就更新 start 吗？
    // 显然不是，如果每次匹配就更新 start ，这在 (()) 这种情况是有效的，但是 ()() 情况就是无效的了
    // 换个角度思考，只要当前子串不合法，我们就更新 start ，我们把 start 的含义转换为了
    // 不合法的子串的 '结束位置' ，那这样 (start + 1) - i 就是合法的子串了，那你会想为什么不将 start 改为 end 呢
    // 实际上这也是可以的，只要你能缕清 start 是用于计算长度，还是表示结束位置，这都是正确的
    // 因为在计算长度时，长度 = (r - (l - 1))，而 start 正好是 l - 1 ，这样就可以直接用 start 来计算了
    // 我们缕清了 start 的含义后，就可以将它的初始值确定，就是 -1
    
    // 3. (())()
    // 这是最难，也是最终需要解决的一个例子。
    // 我们用上面的方法去考虑这个示例，得到的结果将会是 4 ，因为它并没把 [(())][()] 当成一个整体
    // 而是分为了两部分来计算，所以自然是 4 ，因为执行的都是 1
    // 为了解决这个，要将前面两种计算方式缕清才能继续往下走
    // 在官方题解中，我们并不是在确定括号是匹配后(即栈中存在元素)再将左括号出栈
    // 而是在左括号出栈后，才判断是否匹配(栈中是否存在元素)

    // 这其实不大容易想到，但实际上只要你缕清了，也自然而然解决了，接下来用另一个例子来讲述这个方法
    // ((())) ，对，就是这个，就是这个你能用 1 来解决的合法的括号子串
    // 为什么呢？实际上我们在前面考虑这个类型的括号子串时并没有真正考虑清楚
    // 实际上这个括号子串也有一部分在 2 中。
    // ([(())])，这里用中括号将子串分为了两部分
    // 中括号里的部分我们用 1 解决，而中括号外面的部分用 2 来解决，那么怎么才能实现这样的方式呢
    // 这就需要用到刚刚说到的，先弹出栈顶元素，再判断是否匹配(栈中是否存在元素)
    // 你只需要将这个思路应用到 ((())) 上模拟就能想清楚
    // 当我们碰到最后一个 ')' 时，由于采用的是先出栈后匹配，所有最后一个 ')' 是发生不匹配的
    // 所有它走的是 2 用 start 来计算
    
    // 解决了这一部分，知道它如何实现，我们就需要知道它为什么需要这样做
    // 回到 3 的例子 (())() ，现在我们能解决这个问题了
    // 我们仍然将其分为两部分 [(())][()] ，hhh，又回到了 3 最开始的部分了
    // 现在我们将刚刚讨论的，先弹出栈顶元素，再判断是否匹配应用到这里来，你会发现一切都迎刃而解了
    // 第一部分用到了 1 和 2，所以 start 最终保存为 -1 ，而第二部分就只是用到了 2
    // 所以直接用了 start 来计算，**而 start 是 - 1**，这就解决了我们在每次想执行 2 时却执行了 1 的问题
    // 实际上这道题用 栈的思路 最难的一个部分就在于解决 (())() 的问题
    // 看起来 3 最长是一个独立的部分，其实都是在解决 2 方法子程序中没有被用到的问题
    // 也就印证了一开始我说的是两种计算方式而不是一种计算方式的原因
    
    let start = -1;
    for(let i = 0; i < s.length; i++) {
        if(s[i] === ')') {
            // 如果有右括号，但是左括号栈里没有括号，则此时从 start 到 i 都的子串是不合法的，更新 start
            if(!stack.length) {    
                start = i;
            } else {
                stack.pop();      // 解决 2 不执行的问题
                if(stack.length) {// 执行 1
                    max = Math.max(max, i - stack[stack.length - 1]);
                } else {          // 执行 2
                    max = Math.max(max, i - start);
                }
            }
        } else {    // 左括号直接添加它的下标到栈中就好了
            stack.push(i);
        }
    }
    return max;
}
题解 | #最长的括号子串#

一、栈方法
