“Offer comes, ask friends to take it! I am participating in the 2022 Spring Recruit Punch card campaign. Click here for more details.”

1. Title Description

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

Example 1:

Input: s = "(()" Output: 2 Explanation: The longest valid parenthesis substring is "()"Copy the code

Example 2:

Input: s = ")()())" Output: 4 Explanation: The longest valid parenthesis substring is "()()"Copy the code

Example 3:

Input: s = "output: 0Copy the code

Tip:

  • 0 <= s.length <= 3 * 104
  • s[i] 为 '(' 或 ') '

Second, train of thought analysis

We are asked to find the longest valid (well-formed and continuous) parenthesis substring with three constraints: (1) parenthesis combination; ② Return length; ③ The length should be the longest.

My first thought for this parenthesis problem is to use a stack. Power button has a problem is a effective brackets, namely the judgment whether a given string containing only (and) can close, idea is traversal string elements, met (met) is pressed into the stack, elements will stack stack, finally it is ok to determine whether the stack is empty (and, of course, if there are any), the stack is empty, Return false.

This problem is a little harder, but the solution is still stack, but instead of pushing string elements onto the stack, elements are subscript onto the stack. Here’s the idea:

  • will- 1Push (explain why later).
  • Is encountered while iterating through the string element(I just subscript it onto the stack, and I keep iterating;
  • If you encounter)I put the top element on the stackpopIf the stack is not empty, update the length value to be returnedOriginal length 和 Subtract the index of the top element from the index of the current elementIs this why pressing is implemented- 1If you use subscripts to find the length, you will find that the difference is always zero1② If the stack is empty, the index of the current element is added to the stack- 1Same as pushing.
  • Return the length value at the end of the loop.

AC code

Solution 1: Time complexity is O(n), space complexity is O(n)

class Solution {
public:
    int longestValidParentheses(string s) {
        int maxNum = 0;
        stack<int> stk;
        stk.push(- 1);
        for (int i = 0; i < s.size(a); i++) {if (s[i] == '(') {
                stk.push(i);
            } else {
                stk.pop(a);if (stk.empty()) {
                    stk.push(i);
                } else {
                    maxNum = max(maxNum, i - stk.top()); }}}returnmaxNum; }};Copy the code