leetcode
leetcode 951 ~ 1000
删除最外层的括号

删除最外层的括号

难度:

标签:

题目描述

代码结果

运行时间: 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)

代码细节讲解

🦆
在这个算法中,为什么选择使用栈来处理括号而不是其他数据结构如队列或链表?
栈是一种先进后出(LIFO)的数据结构,非常适合处理嵌套结构,如括号匹配问题。这是因为最新加入的左括号必须与接下来遇到的第一个右括号匹配,这与栈的操作特性完全一致。相比之下,队列是先进先出(FIFO)的结构,不适合这种类型的匹配问题,因为它无法灵活地访问最近加入的元素。链表虽然可以从任何位置增加或删除节点,但在此问题中使用链表进行操作会增加不必要的复杂性和开销,因为我们仅需要简单的后进先出操作。
🦆
算法在判断栈是否为空来决定是否将括号添加到结果字符串中的逻辑是怎样的?能否具体解释这一处理步骤?
在算法中,每当遇到一个左括号 '(',会先判断栈是否为空。如果栈不为空,意味着当前左括号是内层括号的一部分,因此应该将其加入到结果字符串中。然后无论栈是否为空,都将该左括号入栈。对于每个右括号 ')',首先将栈顶的左括号出栈,然后再次检查栈是否为空。如果栈不为空,表明当前右括号也是内层括号的一部分,因此将其添加到结果字符串中。这种方式确保只有非最外层的括号被加入到结果字符串中。
🦆
对于输入字符串中连续的多个原语,比如 '(()())(())',这个算法是如何确保每个原语的最外层括号都被正确删除的?
算法通过栈的特性来跟踪每个原语的开头和结束。对于输入 '(()())(())',每当栈从非空变为空时,表明一个原语的最外层括号匹配完成。算法通过在栈为空时不添加括号到结果字符串来确保最外层的括号不被包括,而只有内层括号被添加。因此,每个原语被正确处理,其最外层的括号被排除。
🦆
如果输入的字符串已经没有最外层的括号,例如 '()()()',这个算法的输出是什么?它是否能正确处理这种情况?
对于输入 '()()()',这个字符串实际上是由多个已经没有外层括号的最小单位括号构成的。在这种情况下,算法在处理每对括号时,栈会先入栈一个左括号然后马上出栈,因此每次栈的状态都会从非空变为空,导致不会有任何括号被添加到结果字符串中。所以,算法的输出将是一个空字符串,这是正确的处理结果。

相关问题