力扣00032.最长有效括号

发表于 分类于 阅读次数： 本文字数： 1.6k 阅读时长 ≈ 6 分钟
最长有效括号、栈、字符串、动态规划、困难

题目描述

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

示例 1：

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

示例 2：

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

示例 3：

输入：s = “”
输出：0

提示：

  • $0 <= s.length <= 3 * 10^4$
  • s[i] 为 ‘(‘ 或 ‘)’

解决方法

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> st;
        st.push(-1);
        int maxLen = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (s[i] == '(') {
                st.push(i);
            } else {
                st.pop();
                if (st.empty()) {
                    st.push(i);
                } else {
                    maxLen = max(maxLen, i - st.top());
                }
            }
        }
        return maxLen;
    }
};

结果

执行用时 : 0 ms, 击败 100.00% 使用 C++ 的用户

内存消耗 : 8.35 MB, 击败 14.42% 使用 C++ 的用户

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int maxLen = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    maxLen = Math.max(maxLen, i - stack.peek());
                }
            }
        }
        return maxLen;
    }
}

结果

执行用时 : 6 ms, 击败 26.39% 使用 Java 的用户

内存消耗 : 41.96 MB, 击败 36.08% 使用 Java 的用户

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        stack = [-1]
        max_len = 0
        for i in range(len(s)):
            if s[i] == '(':
                stack.append(i)
            else:
                stack.pop()
                if not stack:
                    stack.append(i)
                else:
                    max_len = max(max_len, i - stack[-1])
        return max_len

结果

执行用时 : 27 ms, 击败 76.27% 使用 Python 的用户

内存消耗 : 11.87 MB, 击败 93.51% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack = [-1]
        max_len = 0
        for i in range(len(s)):
            if s[i] == '(':
                stack.append(i)
            else:
                stack.pop()
                if not stack:
                    stack.append(i)
                else:
                    max_len = max(max_len, i - stack[-1])
        return max_len

结果

执行用时 : 37 ms, 击败 95.99% 使用 Python3 的用户

内存消耗 : 17.03 MB, 击败 36.91% 使用 Python3 的用户

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int longestValidParentheses(char* s) {
    int maxans = 0, n = strlen(s);
    if (n == 0) return 0;
    int dp[n + 1];
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i < n; i++) {
        if (s[i] == ')') {
            if (s[i - 1] == '(') {
                dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
            } else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(') {
                dp[i] = dp[i - 1] +
                        ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
            }
            maxans = fmax(maxans, dp[i]);
        }
    }
    return maxans;
}

结果

执行用时 : 2 ms, 击败 58.87% 使用 C 的用户

内存消耗 : 6.07 MB, 击败 92.90% 使用 C 的用户

C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public int LongestValidParentheses(string s) {
        int maxans = 0;
        int n = s.Length;
        if (n == 0) return 0;
        int[] dp = new int[n];
        for (int i = 1; i < n; i++) {
            if (s[i] == ')') {
                if (s[i - 1] == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && s[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;
    }
}

结果

执行用时 : 42 ms, 击败 91.38% 使用 C# 的用户

内存消耗 : 39.19 MB, 击败 10.35% 使用 C# 的用户

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function(s) {
    let maxLen = 0;
    let stack = [-1];
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(') {
            stack.push(i);
        } else {
            stack.pop();
            if (stack.length === 0) {
                stack.push(i);
            } else {
                maxLen = Math.max(maxLen, i - stack[stack.length - 1]);
            }
        }
    }
    return maxLen;
};

结果

执行用时 : 56 ms, 击败 95.40% 使用 JavaScript 的用户

内存消耗 : 51.18 MB, 击败 13.28% 使用 JavaScript 的用户

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function longestValidParentheses(s: string): number {
    let maxLen: number = 0;
    const stack: number[] = [-1];
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(') {
            stack.push(i);
        } else {
            stack.pop();
            if (stack.length === 0) {
                stack.push(i);
            } else {
                maxLen = Math.max(maxLen, i - stack[stack.length - 1]);
            }
        }
    }
    return maxLen;
}

结果

执行用时 : 53 ms, 击败 97.96% 使用 TypeScript 的用户

内存消耗 : 52.29 MB, 击败 21.43% 使用 TypeScript 的用户

PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {

    /**
     * @param String $s
     * @return Integer
     */
    function longestValidParentheses($s) {
        $maxLen = 0;
        $stack = [-1];
        for ($i = 0; $i < strlen($s); $i++) {
            if ($s[$i] === '(') {
                array_push($stack, $i);
            } else {
                array_pop($stack);
                if (empty($stack)) {
                    array_push($stack, $i);
                } else {
                    $maxLen = max($maxLen, $i - end($stack));
                }
            }
        }
        return $maxLen;
    }
}

结果

执行用时 : 11 ms, 击败 80.00% 使用 PHP 的用户

内存消耗 : 20.43 MB, 击败 6.67% 使用 PHP 的用户

Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    func longestValidParentheses(_ s: String) -> Int {
        var maxLen = 0
        var stack = [-1]
        for (i, char) in s.enumerated() {
            if char == "(" {
                stack.append(i)
            } else {
                stack.popLast()
                if stack.isEmpty {
                    stack.append(i)
                } else {
                    maxLen = max(maxLen, i - stack.last!)
                }
            }
        }
        return maxLen
    }
}

结果

执行用时 : 3 ms, 击败 87.80% 使用 Swift 的用户

内存消耗 : 16.35 MB, 击败 7.32% 使用 Swift 的用户

Kotlin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    fun longestValidParentheses(s: String): Int {
        var maxLen = 0
        val stack = Stack<Int>().apply { push(-1) }
        for (i in s.indices) {
            val char = s[i]
            if (char == '(') {
                stack.push(i)
            } else {
                stack.pop()
                if (stack.isEmpty()) {
                    stack.push(i)
                } else {
                    maxLen = maxOf(maxLen, i - stack.peek())
                }
            }
        }
        return maxLen
    }
}

结果

执行用时 : 175 ms, 击败 66.67% 使用 Kotlin 的用户

内存消耗 : 37.00 MB, 击败 25.00% 使用 Kotlin 的用户

Dart

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
  int longestValidParentheses(String s) {
    int maxLen = 0;
    List<int> stack = [-1];
    for (int i = 0; i < s.length; i++) {
      if (s[i] == '(') {
        stack.add(i);
      } else {
        stack.removeLast();
        if (stack.isEmpty) {
          stack.add(i);
        } else {
          maxLen = max(maxLen, i - stack.last);
        }
      }
    }
    return maxLen;
  }
}

结果

执行用时 : 312 ms, 击败 -% 使用 Dart 的用户

内存消耗 : 147.31 MB, 击败 -% 使用 Dart 的用户

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func longestValidParentheses(s string) int {
	maxLen := 0
	stack := []int{-1}
	for i, char := range s {
		if char == '(' {
			stack = append(stack, i)
		} else {
			stack = stack[:len(stack)-1]
			if len(stack) == 0 {
				stack = append(stack, i)
			} else {
				maxLen = max(maxLen, i-stack[len(stack)-1])
			}
		}
	}
	return maxLen
}
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Go 的用户

内存消耗 : 3.28 MB, 击败 27.17% 使用 Go 的用户

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# @param {String} s
# @return {Integer}
def longest_valid_parentheses(s)
  max_len = 0
  stack = [-1]
  s.each_char.with_index do |char, i|
    if char == '('
      stack.push(i)
    else
      stack.pop
      if stack.empty?
        stack.push(i)
      else
        max_len = [max_len, i - stack.last].max
      end
    end
  end
  max_len
end

结果

执行用时 : 70 ms, 击败 100.00% 使用 Ruby 的用户

内存消耗 : 206.87 MB, 击败 100.00% 使用 Ruby 的用户

Scala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
object Solution {
  def longestValidParentheses(s: String): Int = {
    var maxLen = 0
    var stack = List(-1)
    for ((char, i) <- s.zipWithIndex) {
      if (char == '(') {
        stack = i :: stack
      } else {
        stack = stack.tail
        if (stack.isEmpty) {
          stack = i :: stack
        } else {
          maxLen = math.max(maxLen, i - stack.head)
        }
      }
    }
    maxLen
  }
}

结果

执行用时 : 504 ms, 击败 80.00% 使用 Scala 的用户

内存消耗 : 55.55 MB, 击败 80.00% 使用 Scala 的用户

Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
impl Solution {
    pub fn longest_valid_parentheses(s: String) -> i32 {
        let mut max_len = 0;
        let mut stack = vec![-1];
        for (i, c) in s.chars().enumerate() {
            if c == '(' {
                stack.push(i as i32);
            } else {
                stack.pop();
                if stack.is_empty() {
                    stack.push(i as i32);
                } else {
                    max_len = max_len.max(i as i32 - stack.last().unwrap());
                }
            }
        }
        max_len as i32
    }
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Rust 的用户

内存消耗 : 2.00 MB, 击败 98.53% 使用 Rust 的用户

Racket

1
2
3
4
5
6
7
8
9
10
11
12
13
(define (longest-valid-parentheses s)
  (define max-len 0)
  (define stack (list -1))
  (for ([i (in-range (string-length s))])
    (define char (string-ref s i))
    (cond
      [(char=? char #\() (set! stack (cons i stack))]
      [(char=? char #\))
       (set! stack (cdr stack))
       (if (null? stack)
           (set! stack (list i))
           (set! max-len (max max-len (- i (car stack)))))]))
  max-len)

结果

执行用时 : 187 ms, 击败 100.00% 使用 Racket 的用户

内存消耗 : 97.80 MB, 击败 100.00% 使用 Racket 的用户

Erlang

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Erlang 的用户

内存消耗 : MB, 击败 % 使用 Erlang 的用户

Elixir

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Elixir 的用户

内存消耗 : MB, 击败 % 使用 Elixir 的用户