【leetcode】最长有效括号 O(n)的两种解法

た入场券 2022-03-20 02:40 134阅读 0赞

给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]

--------------------

## 算法思路 ##

方法1  
采用空间换取时间的方法  
先采用O(N)处理标记数组  
采用两个栈分别对括号进行标记以及保存，一个flag数组进行标记。  
如果遇到左括号：左括号和下标进栈  
如果遇到右括号：如果栈顶为左括号，那么当前下标和栈顶下标标记为1，否则右括号进栈  
然后使用O(N)统计连续1的个数

class Solution:
        def longestValidParentheses(self, s):
            """ :type s: str :rtype: int """
            if len(s) <= 1:
                return 0
            flag = [0] * len(s)
            stack = []
            stackIndex = []
            for index, item in enumerate(s):
                if item == '(':
                    stack.append(item)
                    stackIndex.append(index)
                if item == ')':
                    if len(stack) >= 1 and stack.pop() == '(':
                        flag[index], flag[stackIndex.pop()] = 1, 1
                    else:
                        stack.append(item)
            maxLen, start = 0, 0
            while start < len(flag):
                while start < len(flag) and flag[start] == 0:
                    start += 1
                end = start
                while end < len(flag) and flag[end] == 1:
                    end += 1
                maxLen = max(maxLen, end - start)
                start = end + 1
            return maxLen

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70 1]

方法2  
需要定义个start变量来记录合法括号串的起始位置

1.  如果遇到左括号，左括号对应的下标进栈
2.  如果遇到右括号：  
    如果栈空，说明不合法，更改start变量。  
    如果栈不为空，出栈。  
    如果出栈之后栈不为空，长度为max(maxLen, index - stack\[len(stack) - 1\])  
    例如：s = "()(()"遇到右括号，左右括号出栈之后，栈里面仍然有一个左括号，因此长度就是2  
    如果出栈之后栈为空，长度为max(maxLen, index - start + 1)  
    例如s = "()(())"遇到右括号，左右括号出栈之后，栈里面长度为2，但是后面又来了一个又括号，长度就变成了5-0+1=6

class Solution:
        def longestValidParentheses(self, s):
            """ :type s: str :rtype: int """
            if len(s) <= 1:
                return 0
            stack = []
            maxLen, start = 0, 0
            for index, item in enumerate(s):
                if item == '(':
                    stack.append(index)
                if item == ')':
                    if len(stack) == 0:
                        start = index + 1
                    else:
                        stack.pop()
                        maxLen = max(maxLen, index - start + 1) \
                            if len(stack) == 0 else max(maxLen, index - stack[len(stack) - 1])
            return maxLen

这个思路复杂一点，但是少了一次遍历的步骤。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]: /images/20220320/7d08c45005314f099ad040d48e6f9ef5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70 1]: /images/20220320/32549fc5df074ebcbe544fcc07697b4e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70 2]: /images/20220320/4e407fe3d8e04e02a725f4e726c47f65.png