This is the 29th day of my participation in Gwen Challenge

preface

The longest valid parentheses in question 32 are shown below:

Given a string containing only ‘(‘ and ‘)’, find the length of the longest valid (well-formed and continuous) parenthesis substring.

Example 1:

Input: s = “(()” Output: 2 Explanation: The longest valid parenthesis substring is “()”

Example 2:

Input: s = “)()())” Output: 4 Explanation: The longest valid parenthesis substring is “()()”

Example 3:

Input: s = “output: 0

A, thinking

This problem because of this one-to-one correspondence, so at first sight it is natural to think of using stack to solve.

There are two key points to see the longest valid parenthesis, as follows:

  1. Any valid parentheses are)At the end
  2. The length of the valid parentheses is)Minus the subscript of theta(Plus 1Let me give you an example() () ()The length of theta is the subscript5 minus 0 plus 1 is 6

To solve the problem of not knowing the continuity of the substring during iteration, we maintain a starting continuous position at the bottom of the stack (officially called the position of the last closing bracket). This is done to solve a case like ()(()), where the stack only knows that the last one matches the last one to the last (the stack doesn’t know that the last one matches the last one to the last (and that there are no consecutive valid strings). So start with the bottom element of the stack at -1, so that when the last element exits the stack, the current subscript 5 – (-1) yields 6.

For continuity, even if the substring is ()((), it is continuous. When else is continuity broken? Is the current mismatch), such as () () (), the third element) appeared unable to match, so start straight after the third element position becomes the subscript 2

Concrete implementation, mainly in the process of iterating string, there will be the following two cases:

  1. encounter(: pushes the subscript of the current open parenthesis onto the stack
  2. encounter)In first out stacks
    • If the stack is empty: continuity is broken, update the bottom element of the stack to the current subscript.
    • If the stack is not empty: subtract the value of the top element from the current subscript to get the current value)The corresponding(Middle length

For example

Here, s = ())(()) is taken as an example. The specific steps are as follows:

  1. Initializes the bottom element of the stack- 1
  2. Start the iteration and get the first character(.(The subscript0In which case the element in the stack is0, 1
  3. Gets the second character). To the top of the stack0Unstack and decrement the top element of the stack with the current subscript1 minus negative 1 is 2, update resultsret = 2
  4. Gets the third character). To the top of the stack- 1Out of the stack, the stack is empty, update the bottom of the stack starting continuous position is2
  5. Gets the fourth character(.(The subscript3In which case the element in the stack is3, 2
  6. Gets the fifth character(.(The subscript4In which case the element in the stack is4, 3, 2
  7. Gets the sixth character). To the top of the stack4Unstack and decrement the top element of the stack with the current subscript5 minus 3 is 2Without updating the results
  8. Gets the seventh character). To the top of the stack3Unstack and decrement the top element of the stack with the current subscript6 minus 2 is 4, update resultsret = 4

Second, the implementation

The implementation code

The implementation code is consistent with the idea

    /** * Java uses stack implementation */
    public int longestValidParentheses(String s) {
        int ret = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        for (int i=0; i<s.length(); i++) {
            char c = s.charAt(i);
            // open parenthesis on the stack
            if ('(' == c) {
                stack.push(i);
            } else {    // There are two cases of the closing parenthesis
                stack.pop();
                if (stack.isEmpty())    // Does not match the sequential position at the start of the update
                    stack.push(i);
                else    // Update the resultret = Math.max(ret, i - stack.peek()); }}return ret;
    }
Copy the code

The test code

    public static void main(String[] args) {
        int ret = new Number32().longestValidParentheses("()(()");
        System.out.println(ret);
    }
Copy the code

The results of

Third, summary

The stack has a beat rate of less than 50% when executed, which is O(N). After I calmed down, I looked at the top solutions, which basically used dynamic programming. Although the time complexity was also 0(N), I think it did not involve the operation of loading and unloading the stack, resulting in high efficiency.

Thank you to see the end, very honored to help you ~♥