package com.leohacker.leetcode.LongestValidParentheses;

/**
 * 基本的思路是每次遇到右括号，就开始处理前面未处理的左括号。
 *
 * 考虑()这种情况，右括号的出现就吃掉一个左括号，当前长度是2。如果是(())这种情况，在出现第一个右括号的时候，待处理的数据是(2。
 * 这时处理下一个右括号的时候，吃掉左括号，将当前长度加2。这样，一边扫描字符串的过程，就是将左括号和中间结果压栈，出现右括号弹栈的过程。
 * 我们就可以用一个栈来存储未处理的数据。
 *
 * 简化吃括号这个动作，我们可以不将最后出现的当前长度放入栈内。这样每次栈顶都是左括号。
 * 对于()(()这样的例子，未处理的数据是2(2。所以有将计算中的长度压栈的需要。
 * 本来栈应该存放数字和字母的组合，简化实现，将左括号存为1。
 *
 * 由于可能到最后都没有出现可匹配的右括号，所以最后栈中可能还有未处理的数据。
 * 所以在最后要扫描一边栈，找出可能的最大长度。不要忘记还有不在栈里面的当前长度。
 */
public class Solution {
    public int longestValidParentheses(String s) {
        if ( s == null ) {
            return 0;
        }
        int len = s.length();

        // Use the stack to store the incomplete data. The max size for stack is the length of string.
        int[] stack = new int[len];
        int index = 0;              // the pointer to stack.
        int currentLength = 0;      // the current length for right-most valid parentheses.
        int maxLength = 0;

        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if ( c == '(') {
                // if current length exists, push the current length into stack.
                if ( currentLength > 0 ) {
                    stack[index] = currentLength;
                    index++;
                }
                // push the left parentheses into stack.
                stack[index] = 1;
                index++;
                // reset the current length since the left parentheses appears and interrupt the continuation.
                currentLength = 0;
            } else if ( index == 0 ) {  // right parentheses.
                // index == 0 means that we have eaten all left parentheses, orphan right parentheses.
                // calculate the max length and current length.
                maxLength = ( maxLength > currentLength ) ? maxLength : currentLength ;
                // since the orphan parentheses interrupt the continuation, we reset the current length.
                currentLength = 0;
            } else {    // index point to the next empty slot.
                // eat the current left parentheses.
                index--;                // popup the last left parentheses.
                currentLength += 2;     // add the current length.
                // merge the previous length number.
                if ( index > 0 && stack[index-1] != 1 ) {    // if the previous slot is not left parentheses.
                    index--;
                    currentLength += stack[index];
                }
            }
        }

        // scan the stack and calculate the max length.
        for (int i = 0; i < index; i++) {
            if ( stack[i] != 1 ) {
                maxLength = ( maxLength > stack[i]) ? maxLength : stack[i];
            }
        }

        // don't forgot the current length.
        maxLength = ( maxLength > currentLength ) ? maxLength : currentLength ;
        return maxLength;
    }
}

@@ -153,14 +153,13 @@
 %E7%9A%84%E6%97%B6%E5%80%99%EF%BC%8C
-%E5%BE%85
 %E5%A4%84%E7%90%86%E7%9A%84
-%E6%95%B0%E6%8D%AE
+%E7%BB%93%E6%9E%9C
 %E6%98%AF(2%E3%80%82
@@ -466,16 +466,59 @@
 %E9%9D%A2%E7%9A%84%E5%BD%93%E5%89%8D%E9%95%BF%E5%BA%A6%E3%80%82%0A
+ *%0A * %E5%A6%82%E6%9E%9C%E6%A0%88%E4%B8%AD%E6%95%B0%E6%8D%AE%E8%A2%AB%E5%90%83%E5%AE%8C%EF%BC%8C%E5%B0%B1%E8%AE%A1%E7%AE%97%E5%87%BA%E4%B8%80%E6%AE%B5%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E7%BB%93%E6%9E%9C%EF%BC%8C%E5%B0%B1%E5%8F%AF%E4%BB%A5%E8%AE%A1%E7%AE%97%E5%B1%80%E9%83%A8%E7%9A%84%E6%9C%80%E5%A4%A7%E9%95%BF%E5%BA%A6%E3%80%82%0A
  */%0Apubl
@@ -678,16 +678,118 @@
 gth();%0A%0A
+        // give the result ASAP.%0A        if (len == 0 %7C%7C len == 1) %7B%0A            return 0;%0A        %7D%0A%0A
         
@@ -1728,31 +1728,8 @@
  ) %7B
-  // right parentheses.
 %0A   
@@ -1998,16 +1998,37 @@
       //
+ reset current length
  since t
@@ -2079,37 +2079,8 @@
 tion
-, we reset the current length
 .%0A  
@@ -2136,50 +2136,8 @@
 se %7B
-    // index point to the next empty slot.
 %0A   
@@ -2176,32 +2176,140 @@
 left parentheses
+%0A                // decrease the index first since the index point to the next empty slot after last element
 .%0A              

add the comment and optimize.