Share my Java solution


  • 3
    P

    ()()(((....

    We can count the first 2 in only when match the ( after that,

    ()()( .. )

    So just need stack the count when a left parenthesis appear.

    public int longestValidParentheses(String s) {
    	Deque<Integer> stack = new ArrayDeque<Integer>();
    	int longest = 0;
    	int count = 0;
    	for (int i = 0; i < s.length(); i++) {
    		if (s.charAt(i) == '(') {
    			stack.push(count);
    			count = 0;
    		} else if (stack.size() > 0) {
    			count += stack.poll() + 1;
    			longest = Math.max(longest, count);
    		} else {
    			count = 0;
    			stack.clear();
    		}
    	}
    	return longest * 2;
    }

  • 0
    Y

    the solution looks very fast and elegant. Yet what is the intuition for count ? and what is the difference between count and numbers in stack ?

    in count += stack.poll() + 1, what is the meaning of these three numbers ?


Log in to reply
 

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