删除最外层的括号
难度:
标签:
题目描述
代码结果
运行时间: 26 ms, 内存: 15.9 MB
/*
思路:
1. 使用Java Stream API来处理字符串。
2. 使用一个计数器 balance 来追踪左括号和右括号的平衡。
3. 遍历字符串,当遇到左括号时增加计数器,遇到右括号时减少计数器。
4. 当计数器为零时,我们知道我们已经遇到了一个完整的原语。
5. 使用stream和StringBuilder来累积结果。
*/
import java.util.stream.Collectors;
public class Solution {
public String removeOuterParentheses(String s) {
StringBuilder result = new StringBuilder();
int[] balance = {0}; // 使用数组来处理lambda中的变量修改
s.chars().forEach(c -> {
if (c == '(') {
if (balance[0]++ > 0) result.append((char) c);
} else {
if (--balance[0] > 0) result.append((char) c);
}
});
return result.toString();
}
}
解释
方法:
这个题解的思路是使用一个栈来辅助删除最外层的括号。遍历输入字符串,对于每个字符,如果是左括号 '(',则判断栈是否为空,如果不为空,说明这个左括号不是最外层的括号,因此需要将它添加到结果字符串中;然后将这个左括号入栈。如果是右括号 ')',则先出栈一个左括号,然后判断栈是否为空,如果不为空,说明这个右括号不是最外层的括号,因此需要将它添加到结果字符串中。最终返回结果字符串。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在这个算法中,为什么选择使用栈来处理括号而不是其他数据结构如队列或链表?
▷🦆
算法在判断栈是否为空来决定是否将括号添加到结果字符串中的逻辑是怎样的?能否具体解释这一处理步骤?
▷🦆
对于输入字符串中连续的多个原语,比如 '(()())(())',这个算法是如何确保每个原语的最外层括号都被正确删除的?
▷🦆
如果输入的字符串已经没有最外层的括号,例如 '()()()',这个算法的输出是什么?它是否能正确处理这种情况?
▷