【原】LeetCode实战：最长有效括号

老马的程序人生 2020-08-17

展开全文

题目英文

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

题目中文

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"

示例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

示例 3:

输入: ""
输出: 0
解释:

示例 4:

输入: "()(())"
输出: 6
解释: 最长有效括号子串为 "()(())"

算法实现

我们可以用栈在遍历给定字符串的过程中去判断到目前为止扫描的子字符串的有效性，同时计算最长有效字符串的长度。我们首先将 −1 放入栈顶。

对于遇到的每个‘(’，我们将它的下标放入栈中。
对于遇到的每个‘)’，我们弹出栈顶的元素，判断有效性，计算有效长度。

public class Solution {
    public int LongestValidParentheses(string s) {
        Stack<int> stack = new Stack<int>();
        stack.Push(-1);
        int result = 0;
        for (int i = 0; i < s.Length; i++)
        {
            if (s[i] == '(')
            {
                stack.Push(i);
            }
            else
            {
                stack.Pop();
                if (stack.Count == 0)
                {
                    stack.Push(i);
                }
                else
                {
                    result = Math.Max(result, i - stack.First());
                }
            }
        }
        return result;
    }
}