題目英文

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

<b>Example 1</b>:

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

<b>Example 2</b>:

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

題目中文

給定一個(gè)只包含 '(' 和 ')' 的字符串，找出最長(zhǎng)的包含有效括號(hào)的子串的長(zhǎng)度。

<b>示例 1</b>:

輸入: "(()"
輸出: 2
解釋: 最長(zhǎng)有效括號(hào)子串為 "()"

<b>示例 2</b>:

輸入: ")()())"
輸出: 4
解釋: 最長(zhǎng)有效括號(hào)子串為 "()()"

<b>示例 3</b>:

輸入: ""
輸出: 0
解釋: 

<b>示例 4</b>:

輸入: "()(())"
輸出: 6
解釋: 最長(zhǎng)有效括號(hào)子串為 "()(())"

算法實(shí)現(xiàn)

我們可以用棧在遍歷給定字符串的過(guò)程中去判斷到目前為止掃描的子字符串的有效性，同時(shí)計(jì)算最長(zhǎng)有效字符串的長(zhǎng)度。我們首先將 ?1 放入棧頂。

• 對(duì)于遇到的每個(gè)‘(’，我們將它的下標(biāo)放入棧中。
• 對(duì)于遇到的每個(gè)‘)’，我們彈出棧頂?shù)脑?，判斷有效性，?jì)算有效長(zhǎng)度。

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;
    }
}

實(shí)驗(yàn)結(jié)果

• 狀態(tài)：通過(guò)
• 230 / 230 個(gè)通過(guò)測(cè)試用例
• 執(zhí)行用時(shí)：104 ms

提交結(jié)果

相關(guān)圖文：

• LeetCode實(shí)戰(zhàn)：兩數(shù)之和
• LeetCode實(shí)戰(zhàn)：三數(shù)之和
• LeetCode實(shí)戰(zhàn)：缺失的第一個(gè)正數(shù)
• LeetCode實(shí)戰(zhàn)：求眾數(shù)
• LeetCode實(shí)戰(zhàn)：快樂(lè)數(shù)
• LeetCode實(shí)戰(zhàn)：刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)
• LeetCode實(shí)戰(zhàn)：合并兩個(gè)有序鏈表
• LeetCode實(shí)戰(zhàn)：合并K個(gè)排序鏈表
• LeetCode實(shí)戰(zhàn)：兩兩交換鏈表中的節(jié)點(diǎn)
• LeetCode實(shí)戰(zhàn)：旋轉(zhuǎn)鏈表
• LeetCode實(shí)戰(zhàn)：環(huán)形鏈表
• LeetCode實(shí)戰(zhàn)：相同的樹(shù)
• LeetCode實(shí)戰(zhàn)：對(duì)稱二叉樹(shù)
• LeetCode實(shí)戰(zhàn)：二叉樹(shù)的最大深度
• LeetCode實(shí)戰(zhàn)：搜索二維矩陣
• LeetCode實(shí)戰(zhàn)：將有序數(shù)組轉(zhuǎn)換為二叉搜索樹(shù)