删除最外层的括号
栈
-
解题思路：
- 当遇到 ‘(’ 入栈，当遇到 ‘)’ 出栈，当 stack 为空，说明找到了原语；
- 当 stack 不为空的时候，将当前元素放到结果中；
- 由于栈底和栈顶是原语的左右括号，先判断右括号，会跳过将栈底放入结果中，此步骤为优化；
-
复杂度：
- 时间复杂度：O(n)，其中 n 是输入 s 的长度，仅需遍历 s 一次；
- 空间复杂度：O(n)，其中 n 是输入 s 的长度，需要使用栈，长度最大为 O(n)；
-
代码实现：
function removeOuterParentheses(s: string): string { let stack: Array<string> = []; let res: string = ''; for (let i = 0; i < s.length; i++) { if (s[i] === ')') stack.pop(); if (stack.length) res += s[i]; if (s[i] === '(') stack.push(s[i]); } return res; };
双指针
-
解题思路：
- 新建计数双指针，left 记录 ‘(’ 的个数，right 记录 ‘)’ 的个数，当 left === right 时，说明找到了原语；
- 默认 last = 0，记录原语的下一个位置；
- 将原语 [last + 1, j - 1) 加入答案；
-
复杂度：
- 时间复杂度：O(n)，其中 n 是输入 s 的长度，仅需遍历 s 一次；
- 空间复杂度：O(n)，其中 n 是输入 s 的长度，需要使用栈，长度最大为 O(n)；
-
代码实现：
var removeOuterParentheses = function (s) { let left = 0; let right = 0; let last = 0; let res = ''; for (let i = 0; i < s.length; i++) { if (s[i] === '(') left++; if (s[i] === ')') right++; if (left === right) { res += s.slice(last + 1, i).toString(); last = i + 1; } } return res; };
单指针
-
解题思路：
- 新建计数单指针，遇到 ‘(’ 的时候 count++，遇到 ‘)’ 的时候 count–，当 count===0 时，说明找到了原语；
- 默认 last = 0，记录原语的下一个位置；
- 将原语 [last + 1, j - 1) 加入答案；
-
复杂度：
- 时间复杂度：O(n)，其中 n 是输入 s 的长度，仅需遍历 s 一次；
- 空间复杂度：O(n)，其中 n 是输入 s 的长度，需要使用栈，长度最大为 O(n)；
-
代码实现：
var removeOuterParentheses = function (s) { let last = 0; let count = 0; let res = ''; for (let i = 0; i < s.length; i++) { if (s[i] === '(') count++; if (s[i] === ')') count--; if (count === 0) { res += s.slice(last + 1, i).toString(); last = i + 1; } } return res; };
打赏作者
您的打赏是我前进的动力
微信
支付宝
989.数组形式的整数加法
上一篇
评论
