Java stack solution , O(n)


  • 11
    public class Solution {
    public int longestValidParentheses(String s) {
        if(s == null || s.length() <= 1){
            return 0;
        }
        int start = -1;
        int res = 0;
        LinkedList<Integer> stack = new LinkedList<Integer>();
        for(int i=0;i<s.length();i++){
            if(s.charAt(i) == '('){
                stack.push(i);
            }else{
                if(!stack.isEmpty()){
                    stack.pop();
                    if(!stack.isEmpty()){
                        res = Math.max(res,i-stack.peek());
                    }else{
                        res = Math.max(res,i-start);
                    }
                }else{
                    start = i;
                }
            }
        }
        return res;
    }
    

    }


  • 0
    R

    This looks like a very neat solution. Could you please explain what exactly the stack keeps track of and what start keeps track of? I know what's happening but what's the physical significance in words.


Log in to reply
 

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