0032. 最长有效括号

[giscus[bot]]

0032. 最长有效括号

32. 最长有效括号 标签：栈、字符串、动态规划 难度：困难 题目链接 0032. 最长有效括号 - 力扣 题目大意 描述：给定一个只包含 '(' 和 ')' 的字符串。 要求：找出最长有效（格式正确且连续）括号子串的长度。 说明： 0≤s.length≤3∗104。 s[i] 为 '(' 或 ')'。 示例： 示例 1： 示例 2： 解题思路 思...

https://algo.itcharge.cn/Solutions/0001-0099/longest-valid-parentheses/

[YangYishe]

关于栈思路的思考，如何理解这里的stack[-1]?
由于之前已经进行了pop操作，此处的stack[-1]记录的不是)对应的(的位置，而是这之前。可能为(的位置-1。
如果将()视为一层层嵌套的关系，则stack[-1]记录的则是当前层级()的最早计算位置
也因此，需要一个哨兵标记为第一层级的开始计算位置。使用栈进行计算的时候，涉及层级的概念时，均可考虑增加这么一个哨兵，来表示层级的开始计算位置
在此例中，尽管有层级的概念，但最后不一定能构建完整的层级。但这不影响利用层级栈