https://leetcode.com/problems/longest-valid-parentheses/
栈的应用，以及思路转化

个人解答

  1. class Solution:
  2.     def longestValidParentheses(self, s: str) -> int:
  3.         res = 0
  4.         stk = [-1]
  5.         for i, x in enumerate(s):
  6.             if x == '(':
  7.                 stk.append(i)
  8.             else:
  9.                 stk.pop()
  10.                 if not stk:
  11.                     stk.append(i)
  12.                 else:
  13.                     res = max(res, i - stk[-1])
  14.         return res

题目分析

括号匹配问题，属于比较明显的栈的应用问题。
找到长的一段匹配的括号比较直接，关键是处理并列的情况。

最开始的思路，记录下以每个位置结尾的最长valid段，然后每次有新的段之后，加上前边的段：

  1. class Solution:
  2.     def longestValidParentheses(self, s: str) -> int:
  3.         res = 0
  4.         curr = 0
  5.         stk = []
  6.         segments = defaultdict(int)
  7.         for i, x in enumerate(s):
  8.             if x == '(':
  9.                 stk.append(i)
  10.             else:
  11.                 if not stk:
  12.                     continue
  13.                 segments[i] = i - stk[-1] + 1 + segments[stk[-1] - 1]
  14.                 stk.pop()
  16.         return max(segments.values()) if segments else 0

但其实这道题可以转变下思路：找最长的valid段，其实两个invalid中间的都是valid的，所以只要记录上一个不是valid的index就好了。最开始的invalid index是-1，之后遇到)多出的invalid情况，更新invalid index。
最终解法如题解中的代码所示。