Java solution - using minus to denote ")" location.


  • 2
    W
    public int longestValidParentheses(String s) {
        Stack<Integer> stack=new Stack<Integer>();
        int max=0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='(') stack.push(i);
            else{ //')'
             if(stack.isEmpty() || stack.peek()<0)
                stack.push(-1-i); 
             else{
                stack.pop();
                if(stack.isEmpty()) max=Math.max(max,i+1);
                else{
                    int last=stack.peek();
                    if(last<0)
                        last = -1-last;
                    max=Math.max(max,i-last);
                }
             }
            }
        }
        return max;
    }

  • 0
    J

    Smart! Thanks for sharing.


Log in to reply
 

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