问题描述

给出一个只包含左右小括号的字符串，要求找出其中最长的合法的括号对的子字符串，返回其长度。题目链接：**点我**

样例输入输出

输入：”)()())”

输出：4

输入：”()(()”

输出：2

问题解法

此解法主要参考 leetcode 上文章的解法三（用 stack 进行求解），详细参考点击**这里**

主要过程如下：

定义一个栈，用来存储字符串的下标。初始化压入数值 -1
遍历字符串，对每个字符执行以下操作
- 如果当前字符是(，则直接将当前下标压入栈中
- 如果当前字符是)，则将栈顶元素出栈，然后判断栈是否为空，如果为空，则将当前下标压入栈中，否则用当前下标减去栈顶值，得到当前匹配到的括号的长度，将此值与保存的最大长度进行比较，取其最大值更新最大长度变量的值

现在证明此方法的可行性：

首先，从算法流程中，可以很容易得出以下结论：

当栈顶元素对应的字符是)时，栈中必然只有一个元素。因为)只有在栈中元素为空时才会将下标入栈。
当栈顶元素对应的字符是(时，栈中元素必然大于一个。原因同上。
当栈顶元素对应的字符是)时，以当前字符为截止字符构成的子字符串一定不能组成一个合法的括号对，即)数量多于(数量。因为每次遇到(都会将其下标入栈，而遇到)都会弹出一个元素，如果(与)数量相等，则栈顶元素为 -1，如果(数量比)多，则栈顶对应字符是(。
当栈顶元素多于一个时，次栈顶元素在原字符串对应的元素必然是栈顶元素在原字符串中对应的元素的的前一个元素（*-1 当作是第 0 个元素的前一个元素*）。因为当栈中元素多于一个时，如果次栈顶是 -1，则栈顶一定 0（因为所有(都会压入栈中，如果第0个元素是),则会将 -1 出栈），如果次栈顶对应的元素是(，则次栈顶和栈顶对应的元素必然是相邻的（因为所有(都会压入栈中），如果次栈顶对应元素是)，由于连续多个)字符时，栈中也只会保留最后一个)的下标，所以次栈顶和栈顶对应的元素也是相邻的。

其次，证明循环中遇到)，其计算结果的准确性：

如果栈中只有一个元素，即栈顶元素对应字符是)，说明当前字符前面组成的字符不能全部构成合法括号对字符串，因此，截止到当前字符构成的子字符串也无法构成一个合法的括号对字符串，故不用更新最大合法括号对字符串长度变量的值。
如果栈中多于一个元素，即栈顶元素对应字符是(，说明从当前栈顶元素对应的字符到当前元素构成的子字符串是一个合法的括号对字符串（由于这个子字符串中间已经经过了上述的判断，如果中间某个元素 k 与栈顶元素构成的字符串不是一个合法的括号对字符串，则栈顶元素是 k 而不是现在这个，因此可以保证栈顶元素到当前元素构成的子字符串是一个合法的括号对字符串），所以只需要算出当前子字符串的长度跟最大合法括号对字符串长度进行比较即可。由于次栈顶元素必然是栈顶元素的前一个元素，所以用当前元素下标减去栈顶元素可以算出当前子字符串的长度。

代码如下：

class Solution 
{
    public int longestValidParentheses(String s) 
    {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int length = s.length();
        int num = 0;
        int maxNum = 0;
        for (int i = 0; i < length; i++)
        {
            if (s.charAt(i) == '(')
            {
                stack.push(i);
            }
            else
            {
                stack.pop();
                if (stack.empty())
                {
                    stack.push(i);
                }
                else 
                {
                    num = i - stack.peek();
                    if (num > maxNum)
                    {
                        maxNum = num;
                    }
                }
            }
        }
        
        return maxNum;
    }
}

参考来源

https://leetcode.com/articles/longest-valid-parentheses/

ChunNote

leetCode-32:Longest Valid Parentheses

问题描述

样例输入输出

问题解法

参考来源