【经典算法题】最长有效括号
2021/12/19 17:20:19
本文主要是介绍【经典算法题】最长有效括号,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
【经典算法题】最长有效括号
Leetcode 0032 最长有效括号
题目描述:Leetcode 0032 最长有效括号
分析
-
本题的考点:栈。
-
首先,对于只含有小括号的序列,我们应该清楚序列时合法的,需要满足两个条件:
(1)左右括号数量相等;
(2)任意前缀中左括号数量一定大于等于右括号数量。
-
第一步我们应该将整个括号序列分段:从左向右找到第一个前缀中右括号数量大于左括号数量的位置,这个前缀是第一个分段;然后继续对后面的序列进行这样的操作,这样我们可以将整个序列划分成多个分段,可以证明最长的有效括号的不会跨越多个段,只能在段内,如下图:
- 下面证明最长的有效括号的不会跨越多个段,可以使用反证法:
-
之后我们可以使用一个栈记录所有的左括号下标,遇到左括号直接将其下标入栈。
-
遇到右括号分为两种情况讨论:
(1)如果栈非空,将栈顶元素出队,如果出队之后栈非空则此时栈顶元素的下一个位置到当前位置是有效括号,如果栈为空则从该段的起始位置到当前位置是有效括号;
(2)如果栈为空,说明遇到右括号但是没有可以匹配的左括号,该段结束,进行下一段。
代码
- C++
class Solution { public: int longestValidParentheses(string s) { stack<int> stk; int res = 0; for (int i = 0, start = -1; i < s.size(); i++) { // start为每段起始位置的前一个位置 if (s[i] == '(') stk.push(i); else { // 说明是右括号 if (stk.size()) { // (1) 栈非空 stk.pop(); if (stk.size()) res = max(res, i - stk.top()); else res = max(res, i - start); } else { // (2) 栈空, 说明遇到右括号但是没有可以匹配的左括号,该段结束,进行下一段 start = i; } } } return res; } };
- Java
class Solution { public int longestValidParentheses(String s) { Deque<Integer> stk = new ArrayDeque<>(); char[] cs = s.toCharArray(); int res = 0; for (int i = 0, start = -1; i < cs.length; i++) { // start为每段起始位置的前一个位置 if (cs[i] == '(') stk.push(i); else { // 说明是右括号 if (!stk.isEmpty()) { // (1) 栈非空 stk.pop(); if (!stk.isEmpty()) res = Math.max(res, i - stk.peek()); else res = Math.max(res, i - start); } else { // (2) 栈空, 说明遇到右括号但是没有可以匹配的左括号,该段结束,进行下一段 start = i; } } } return res; } }
- Python
class Solution: def longestValidParentheses(self, s: str) -> int: stk = [] start = -1 res = 0 for i in range(len(s)): if s[i] == '(': stk.append(i) else: if len(stk) != 0: stk.pop(len(stk) - 1) if len(stk) != 0: res = max(res, i - stk[len(stk) - 1]) else: res = max(res, i - start) else: start = i return res
时空复杂度分析
-
时间复杂度: O ( n ) O(n) O(n),
n
为字符串s
的长度。 -
空间复杂度: O ( n ) O(n) O(n),
n
为字符串s
的长度。
这篇关于【经典算法题】最长有效括号的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南