Very clean code with Chinese comment


  • 0
    W

    思路1:利用栈来做括号匹配的问题(栈中存储下标而非括号,因为我们可以用下标来找到括号),每当遇到无法匹配的括号时,我们记录他们之间的距离(下标之间的差 - 1),最大的距离就是解。
    solution1:Use a stack to do bracket-matching(instead of storing bracket, we store index since we could use index to index the bracket), each time we can't match two brackets, we record their distence(the difference between two indexes), the max distence is the solution.
    for example:

    s = "(()(",  max = 0, dif = 0 // max is the result, dif is the distence of two mismacth bracket
    step 0: stack = []
            i = 0, s[i] = '('  // i is the index we currently process
    step 1: stack = [0]        // s.charAt(0) = '(', we store index of '('
            i = 1, s[i] = '('  dif = i - stack.peek() - 1 = 0 // mismatch of s[stack.peek()] and s[i]
            max = Math.max(max, dif) = 0
    step 2: stack = [0, 1]
            i = 2, s[i] = ')'  stack.pop()         // match of s[stack.peek()] and s[i]
    step 3: stack = [0]
            i = 3, s[i] = '('  dif = i - stack.peek() - 1 = 2 // mismatch of s[stack.peek()] and s[i]
            max = Math.max(max, dif) = 2
    step 4: ...
    
    public class Solution {
        public int longestValidParentheses(String s) {
             Deque<Integer> stack = new ArrayDeque<>(s.length());
             if(s == null) return 0;
             int max = 0;
             stack.push(-1);  // 用一个哨兵, as a guard
             for(int i = 0; i < s.length(); i++) {
                 if(s.charAt(i) == ')' && stack.size() != 1 && s.charAt(stack.peek()) == '(')  {  // match
                     stack.pop();
                 } else {  // mismatch
                     max = Math.max(max, i - stack.peek() - 1);
                     stack.push(i);
                 }
             }
             return Math.max(max, s.length() - stack.pop() - 1);
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.