题目描述

原题链接

给你一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：
输入：s = “(()”
输出：2
解释：最长有效括号子串是 “()”

示例 2：
输入：s = “)()())”
输出：4
解释：最长有效括号子串是 “()()”

示例 3：
输入：s = “”
输出：0

提示：

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

  个人解法

Javascript

暴力解法，目前是我最优化之后的暴力解法，但是还是超时了

/*
 * @lc app=leetcode.cn id=32 lang=javascript
 *
 * [32] 最长有效括号
 */
// @lc code=start
var check = function (s, left, right) {
  const arr = [];
  let top = -1;
  if (s[left] === ')' || s[right] === '(') {
    return false;
  }
  for (let i = left; i <= right; i++) {
      if(top)
    if (top > -1 && arr[top] === '(' && s[i] === ')') {
      arr.pop();
      top--;
    } else {
      arr.push(s[i]);
      top++;
    }
  }
  return arr.length === 0;
}
/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function (s) {
  if (s.length < 2) {
    return 0;
  }
  let left = 0;
  let right = s.length - 1;
  while (s[left] !== '(' && left < s.length) left++;
  while (s[right] !== ')' && right > 0) right--;
  let max = 0;
  while (left <= right) {
    let i = left;
    if(s[left] === ')'){
        left ++;
        continue;
    }
    if (max > right - i + 1) {
      break;
    }
    let j = (right - i + 1) % 2 === 0 ? right : right - 1;
    for (; j > i; j -= 2) {
      if (max > j - i + 1) {
        break;
      }
      if (check(s, i, j)) {
        max = Math.max(max, j - i + 1);
        left = j;
        break;
      }
    }
    console.log(left);
    left ++;
  }
  return max;
};
// @lc code=end

Java(栈）

class Solution {
    public int longestValidParentheses(String s) {
        char[] chars=s.toCharArray();
        int len=s.length(),max=0,n=-1;
        Stack<Integer> stack=new Stack<>();
        stack.push(-1);
        for (int i=0;i<len;i++){
            //()(()()-1
            if (chars[i]=='('){
                stack.push(i);
            }else {
                stack.pop();
                if (stack.empty()){
                    stack.push(i);
                }else {
                    max=Math.max(max,i-stack.peek());
                }
            }
        }
        return max;
    }
}

其他解法

Java

动态规划

class Solution {
    public int longestValidParentheses(String s) {
        int maxans = 0;
        int[] dp = new int[s.length()];
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                maxans = Math.max(maxans, dp[i]);
            }
        }
        return maxans;
    }
}

class Solution {
    public int longestValidParentheses(String s) {
        int left = 0, right = 0, maxlength = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxlength = Math.max(maxlength, 2 * right);
            } else if (right > left) {
                left = right = 0;
            }
        }
        left = right = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxlength = Math.max(maxlength, 2 * left);
            } else if (left > right) {
                left = right = 0;
            }
        }
        return maxlength;
    }
}

Javascript

动态规划

const longestValidParentheses = (s) => {
  let maxLen = 0;
  const len = s.length;
  const dp = new Array(len).fill(0);
  for (let i = 1; i < len; i++) {
    if (s[i] == ')') {
      if (s[i - 1] == '(') {
        if (i - 2 >= 0) {
          dp[i] = dp[i - 2] + 2;
        } else {
          dp[i] = 2;
        }
      } else if (s[i - dp[i - 1] - 1] == '(') {
        if (i - dp[i - 1] - 2 >= 0) {
          dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2];
        } else {
          dp[i] = dp[i - 1] + 2;
        }
      }
    }
    maxLen = Math.max(maxLen, dp[i]);
  }
  return maxLen;
};

栈

/*
 * @lc app=leetcode.cn id=32 lang=javascript
 *
 * [32] 最长有效括号
 */
// @lc code=start
/**
 * @param {string} s
 * @return {number}
 */
const longestValidParentheses = (s) => {
  let maxLen = 0;
  const len = s.length;
  const stack = [-1];
  let index = 0;
  for (let i = 0; i < len; i++) {
    if (s[i] === '(') {
      stack.push(i);
      index++;
    } else {
      stack.pop();
      index--;
      if (index > -1) {
        maxLen = Math.max(maxLen, i - stack[index]);
      } else {
        stack.push(i);
        index++;
      }
    }
  }
  return maxLen;
};
// @lc code=end