[アルゴリズムベース]スタック関連-最長有効かっこ

タイトル

「(」と「)」のみを含む文字列を指定し、有効なカッコを含む最長のサブ列の長さを見つけます.
例1:

  : "(()"
  : 2
  :           "()"

例2:

  : ")()())"
  : 4
  :           "()()"

問題を解く構想.

スタックを介して,所与の文字列を遍歴する過程で,現在位置のサブ列の有効性を判断することができる.次に、最長有効長を更新します.具体的なやり方.

出会った(ごとに、私たちは彼の下付き記号をスタックに入れた.

)にスキャンされると、1回ポップアップされ、現在のインデックス-スタックインデックス+1が記録され、最大値が更新されます.

しかし、例2では、最初にスキャンしたのは)であり、スタックが空で、ポップアップできません.また、スキャン中にスタックが空であれば、)に再び遭遇し、下に進むこともできません.したがって、スタックがスキャン全体で空でなく、計算可能であることを確認するために、参照物を設定する必要があります.

スキャン開始時にスタック内の初期要素を-1に設定し、(())のような文字列をスムーズにスキャンすれば、有効長は3-(-1) = 4であり、このとき-1はスタックトップ値である.

スキャン開始時にスタック内の初期要素を-1として設定し、)())のような文字列を描くと)が直接-1アウトスタックに遭遇した場合、スタックは空であり、再びスタックに入った(のインデックスである1であれば、)アウトスタックに再び遭遇した場合、計算はエラーとなり、長さは2-1 = 1となる.したがって、有効な長さを計算するために参照要素も必要です.スタックが空のときに遭遇する右括弧のインデックスを参照要素として選択することができ、次のスタック(のインデックスよりもちょうど1小さい.計算を統一しやすい.

は、連続する)に遭遇し、前の参照要素も絶えずポップアップされます.ポップアップメカニズムは、スタック内の参照要素を保持するときに、次の(に最も近い要素を保持することができる.

/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function(s) {
     
    var maxLen = 0;
    const stack = [-1];
    for (let i = 0; i < s.length; i++) {
     
        const c = s[i];
        if (c == '(') {
          //          
            stack.push(i);
            continue;       //   ，       
        }
        stack.pop();        //      ，    
        if (stack.length == 0) {
         //     ，         
            stack.push(i);          //       “   ” 
        } else {
                         //        ，         ，    
            maxLen = Math.max(maxLen, i - stack[stack.length - 1]);
        }
    }
    return maxLen;
};