最长有效括号

GitHub跳转原题关系图返回列表

栈保存未匹配位置，弹出后用栈顶计算有效长度，栈空时压入当前右括号作为新边界。

OJ: leetcodecn

题目 ID: longest-valid-parentheses

难度:提高+/省选-

标签:栈动态规划字符串

日期: 2026-07-29 12:48

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

求最长有效括号子串的长度。

思路

栈中保存下标。初始压入 -1 作为虚拟边界。遇到 ( 压入下标；遇到 ) 弹出栈顶，若栈空则压入当前下标作为新边界，否则用当前下标减去栈顶计算有效长度。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> st;
        st.push(-1);
        int ans = 0;
        for (int i = 0; i < (int)s.size(); i++) {
            if (s[i] == '(')
                st.push(i);
            else {
                st.pop();
                if (st.empty())
                    st.push(i);
                else
                    ans = max(ans, i - st.top());
            }
        }
        return ans;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    cout << Solution().longestValidParentheses(s) << '\n';
    return 0;
}
python
#!/usr/bin/env python3
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        st = [-1]
        ans = 0
        for i, ch in enumerate(s):
            if ch == "(":
                st.append(i)
            else:
                st.pop()
                if not st:
                    st.append(i)
                else:
                    ans = max(ans, i - st[-1])
        return ans


def main():
    print(Solution().longestValidParentheses(input().strip()))


if __name__ == "__main__":
    main()

复杂度

  • 时间复杂度：O(n)O(n)。
  • 空间复杂度：O(n)O(n)。

总结

栈解法的关键是栈中始终保存"最后一个未被匹配的右括号下标"作为边界。弹出后栈顶就是有效子串的起点前一个位置，差值即为长度。