如果问题解决后帮助程序堆栈几乎完全删除，那么 space 复杂度是多少？

Question

我正在解决“有效括号”leetcode 问题 (#20) 并且我运行进入这个看起来非常有效的解决方案 - 它使用一个辅助堆栈，如果括号都有效。

我想知道 space 复杂度是否大约为 O(N) 或更小？我很困惑，主要是因为辅助堆栈通常在最后被删除，但我知道这不会是最坏的情况，所以我不太确定。

这是代码：

class Solution {
    
public boolean isValid(String s) {
    
    Stack<Character> stack = new Stack<Character>();
    
    for (char c : s.toCharArray()) {
        if (c == '(')
            stack.push(')');
        else if (c == '{')
            stack.push('}');
        else if (c == '[')
            stack.push(']');
        else if (stack.isEmpty() || stack.pop() != c)
            return false;
    }
    
    return stack.isEmpty();
    
    }
}

谢谢！

Answer 1

I'm confused mostly because the helper stack is usually deleted at the end

这不是最终堆栈中的内容，而是堆栈中的内容在处理过程中。想象一个字符串 ((((((()))))))（一个有效的括号序列）。即使堆栈最后是空的，它也会在解决方案的中途包含 N/2 个字符，即 O(N/2) 在渐近复杂度中是 O(N)。

另请记住，最好的情况通常不是很有用。我想最好的情况是 ()()() ，在任何时候你在堆栈中只有 1 个字符。但是因为我们很少关心最好的情况，所以我们想要最坏或预期的情况，即 O(N)。

所以答案就是 O(N)。

如果问题解决后帮助程序堆栈几乎完全删除，那么 space 复杂度是多少？

If a helper stack almost completely deletes after problem is solved, what is the space complexity?

java

data-structures

stack

space-complexity