最长有效括号

题目要求

给定一个只包含字符 '(' 和 ')' 的字符串，任务是找出这个字符串中最长的有效括号子串的长度。有效括号子串指的是括号能正确匹配的连续序列。

解题思路

要解决这个问题，我们可以采用以下几种思路：

栈的应用：
- 创建一个栈来跟踪未匹配的括号。
- 遍历字符串，对于每个字符：
  - 如果是 '('，将其索引压入栈。
  - 如果是 ')'：
    - 弹出栈顶元素（如果栈不为空），这表示匹配了一个括号对。
    - 如果栈为空，说明没有与当前 ')' 匹配的 '('，将当前索引压入栈作为新的起点。
    - 如果栈不为空，计算当前有效子串的长度（当前索引 - 栈顶元素索引），并更新最长有效括号子串的长度。
- 栈中始终保持的是未匹配括号的索引，这样可以通过索引差来计算长度。
动态规划：
- 创建一个和输入字符串等长的数组 dp，dp[i] 表示以 i 结尾的最长有效括号子串的长度。
- 遍历字符串，对于每个 ')' 字符：
  - 如果它前面的字符是 '('，则形成了一个有效对，dp[i] = dp[i-2] + 2。
  - 如果它前面的字符也是 ')' 并且它前面的有效子串前面是 '('，则形成了一个更长的有效子串，dp[i] = dp[i-1] + dp[i - dp[i-1] - 2] + 2。
- 在遍历过程中，记录 dp 数组中的最大值，这就是最长有效括号子串的长度。
双向扫描：
- 从左到右和从右到左各扫描一次字符串。
- 在每次扫描中，用两个变量 left 和 right 分别记录遇到的 '(' 和 ')' 的数量。
- 在从左到右扫描时，每当 left 和 right 相等时，更新最长有效括号子串的长度；如果 right 大于 left，则重置两个计数器。
- 在从右到左扫描时，执行相同的操作，但如果 left 大于 right，则重置两个计数器。
- 这种方法的优点是不需要额外的空间，但需要两次遍历。

以上三种方法中，栈的方法和动态规划的方法都能得到准确的结果，而双向扫描的方法在某些情况下更高效，但需要注意正确处理计数器的重置。根据具体情况选择合适的方法来实现。

Golang 版本

package main

import (
	"fmt"
)

func longestValidParentheses(s string) int {
    var maxLen int
    stack := []int{-1} // 初始化栈，先放入-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 {
                // 如果栈不为空，计算当前有效子串的长度
                // 并更新最长有效括号子串的长度
                currentLen := i - stack[len(stack)-1]
                if currentLen > maxLen {
                    maxLen = currentLen
                }
            }
        }
    }

    return maxLen
}

func main() {
    // 示例
    s := "(()())"
    fmt.Println("最长有效括号子串的长度为:", longestValidParentheses(s))
}

这段代码使用了栈的方法来解决问题。它初始化一个栈，并在栈底预先放入一个-1 作为基准点。这样做是为了方便计算有效子串的长度。当遇到左括号时，将其索引压入栈中；遇到右括号时，尝试弹出栈顶元素，并根据栈的状态更新最长有效括号子串的长度。如果栈为空，则将当前索引压入栈中，这表示之前的所有括号都已匹配，当前的右括号没有匹配的左括号，需要重新设置一个新的起点。

C++版本

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int longestValidParentheses(string s) {
    int maxLen = 0;
    stack<int> stk;
    stk.push(-1); // 初始化栈，先放入-1作为参照点

    for (int i = 0; i < s.length(); ++i) {
        if (s[i] == '(') {
            // 如果是左括号，将索引压入栈
            stk.push(i);
        } else {
            // 如果是右括号，弹出栈顶元素
            stk.pop();
            if (stk.empty()) {
                // 如果栈为空，将当前索引压入栈
                stk.push(i);
            } else {
                // 如果栈不为空，计算当前有效子串的长度
                // 并更新最长有效括号子串的长度
                maxLen = max(maxLen, i - stk.top());
            }
        }
    }

    return maxLen;
}

int main() {
    // 示例
    string s = "(()())";
    cout << "最长有效括号子串的长度为: " << longestValidParentheses(s) << endl;
    return 0;
}

这段 C++代码同样采用了栈的方法来解决最长有效括号子串的问题。它首先创建一个栈，并将-1 压入栈中作为基准点。然后遍历字符串，遇到左括号时将其索引压入栈中，遇到右括号时尝试弹出栈顶元素。如果栈为空，则将当前索引压入栈中作为新的起点。如果栈不为空，则计算当前有效子串的长度，并更新最长有效括号子串的长度。最终返回最大长度作为结果。

Python 版本

def longest_valid_parentheses(s):
    max_len = 0
    stack = [-1]  # 初始化栈，先放入-1作为参照点

    for i, char in enumerate(s):
        if char == '(':
            # 如果是左括号，将索引压入栈
            stack.append(i)
        else:
            # 如果是右括号，弹出栈顶元素
            stack.pop()
            if not stack:
                # 如果栈为空，将当前索引压入栈
                stack.append(i)
            else:
                # 如果栈不为空，计算当前有效子串的长度
                # 并更新最长有效括号子串的长度
                max_len = max(max_len, i - stack[-1])

    return max_len

# 示例
s = "(()())"
print("最长有效括号子串的长度为:", longest_valid_parentheses(s))

这段 Python 代码使用了栈的方法来解决最长有效括号子串的问题。它首先创建一个栈，并将-1 压入栈中作为基准点。然后遍历字符串，遇到左括号时将其索引压入栈中，遇到右括号时尝试弹出栈顶元素。如果栈为空，则将当前索引压入栈中作为新的起点。如果栈不为空，则计算当前有效子串的长度，并更新最长有效括号子串的长度。最终返回最大长度作为结果。

Java 版本

import java.util.Stack;

public class Solution {
    public int longestValidParentheses(String s) {
        int maxLen = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1); // 初始化栈，先放入-1作为参照点

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                // 如果是左括号，将索引压入栈
                stack.push(i);
            } else {
                // 如果是右括号，弹出栈顶元素
                stack.pop();
                if (stack.empty()) {
                    // 如果栈为空，将当前索引压入栈
                    stack.push(i);
                } else {
                    // 如果栈不为空，计算当前有效子串的长度
                    // 并更新最长有效括号子串的长度
                    maxLen = Math.max(maxLen, i - stack.peek());
                }
            }
        }

        return maxLen;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String s = "(()())";
        System.out.println("最长有效括号子串的长度为: " + solution.longestValidParentheses(s));
    }
}

这段 Java 代码使用了栈的方法来解决最长有效括号子串的问题。它首先创建一个栈，并将-1 压入栈中作为基准点。然后遍历字符串，遇到左括号时将其索引压入栈中，遇到右括号时尝试弹出栈顶元素。如果栈为空，则将当前索引压入栈中作为新的起点。如果栈不为空，则计算当前有效子串的长度，并更新最长有效括号子串的长度。最终返回最大长度作为结果。

Rust 版本

fn longest_valid_parentheses(s: String) -> i32 {
    let mut max_len = 0;
    let mut stack: Vec<i32> = vec![-1]; // 初始化栈，先放入-1作为参照点

    for (i, char) in s.chars().enumerate() {
        if char == '(' {
            // 如果是左括号，将索引压入栈
            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
}

fn main() {
    // 示例
    let s = String::from("(()())");
    println!("最长有效括号子串的长度为: {}", longest_valid_parentheses(s));
}

这段 Rust 代码使用了栈的方法来解决最长有效括号子串的问题。它首先创建一个栈，并将-1 压入栈中作为基准点。然后遍历字符串，遇到左括号时将其索引压入栈中，遇到右括号时尝试弹出栈顶元素。如果栈为空，则将当前索引压入栈中作为新的起点。如果栈不为空，则计算当前有效子串的长度，并更新最长有效括号子串的长度。最终返回最大长度作为结果。

总结

上述解法采用了栈（Stack）这一数据结构来解决最长有效括号子串的问题。核心思想是利用栈来跟踪和匹配每个括号的位置。具体步骤如下：

初始化一个栈，并将一个特殊值（通常是-1）压入栈中作为基准点，这个值代表的是最后一个没有被匹配的右括号的位置。
遍历字符串中的每个字符：
- 如果当前字符是左括号 '('，则将其索引压入栈中。
- 如果当前字符是右括号 ')'：
  - 首先弹出栈顶元素，这代表尝试匹配一个左括号。
  - 如果弹出栈顶元素后栈为空，说明没有左括号与当前右括号匹配，此时将当前字符的索引压入栈中，更新最后一个没有被匹配的右括号的位置。
  - 如果栈不为空，则说明栈顶元素是与当前右括号匹配的左括号的索引，此时可以计算当前有效括号子串的长度（当前索引减去栈顶元素的值），并更新最长有效括号子串的长度。
遍历完成后，得到的最长有效括号子串的长度即为所求。

这种方法的时间复杂度为 O(n)，空间复杂度也为 O(n)，其中 n 是字符串的长度。这是因为每个字符最多被压入和弹出栈一次。

这个算法的关键在于：

使用栈来处理括号的匹配问题。
使用栈底元素来记录最后一个未匹配的右括号的位置。
在遍历过程中，不断更新最长有效括号的长度。

这个解法是通用的，可以用在任何支持栈这一数据结构的编程语言中，如上面提供的 C++, Python, Java, 和 Rust 版本的代码。

hot-100