标签： 栈

3174.清除数字 – 双端队列

目标

给你一个字符串 s 。

你的任务是重复以下操作删除 所有 数字字符：

  • 删除 第一个数字字符 以及它左边 最近 的 非数字 字符。

请你返回删除所有数字字符以后剩下的字符串。

示例 1：

输入：s = "abc"
输出："abc"
解释：
字符串中没有数字。

示例 2：

输入：s = "cb34"
输出：""
解释：
一开始，我们对 s[2] 执行操作，s 变为 "c4" 。
然后对 s[1] 执行操作，s 变为 "" 。

说明：

  • 1 <= s.length <= 100
  • s 只包含小写英文字母和数字字符。
  • 输入保证所有数字都可以按以上操作被删除。

思路

删除给定字符串中的数字字符，每次删除操作需要同步删除该字符左侧最后一个非数字字符。

遍历的过程中使用栈保存非数字字符，遇到数字字符就弹栈，然后返回栈底到栈顶的字符即可。

知识点：

  • ArrayDeque 双端队列的特性取决于如何放入数据

                    start
         last           first
offer       4 3 2 1
push              1 2 3 4

  • offer是向左添加数据

  • push是向右添加数据

  • poll/pop/remove 默认从右向左取数据

  • 如果api中带last，例如pollLast、removeLast则是从左向右取，first则相反

代码


/**
 * @date 2024-09-05 8:47
 */
public class ClearDigits3174 {

    public String clearDigits(String s) {
        int n = s.length();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c > '9' || c < '0') {
                sb.append(c);
            } else {
                sb.deleteCharAt(sb.length() - 1);
            }
        }
        return sb.toString();
    }

}

性能

232.用栈实现队列

目标

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

  • 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
  • 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 1：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]

输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

说明：

  • 1 <= x <= 9
  • 最多调用 100 次 push、pop、peek 和 empty
  • 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）

进阶：

你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。

思路

这道题是让我们仅使用push压入栈顶、peek获取栈顶元素、pop弹栈等API实现先进先出队列。

关键是要想明白一点，入栈与出栈操作的是不同的栈，出栈s2中的元素是从入栈s1中获取的，并且，只能在s2为空的时候，将s1中的元素一个个弹栈再入s2，这样才能保证顺序反转。

代码

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @date 2024-03-04 0:42
 */
public class MyQueue {
    private final Deque<Integer> s1;
    private final Deque<Integer> s2;

    public MyQueue() {
        s1 = new ArrayDeque<>();
        s2 = new ArrayDeque<>();
    }

    public void push(int x) {
        s1.push(x);
    }

    public int pop() {
        if (s2.isEmpty()) {
            while (!s1.isEmpty()) {
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }

    public int peek() {
        if (s2.isEmpty()) {
            while (!s1.isEmpty()) {
                s2.push(s1.pop());
            }
        }
        if (s2.isEmpty()) {
            throw new RuntimeException();
        }
        return s2.peek();
    }

    public boolean empty() {
        return s2.isEmpty() && s1.isEmpty();
    }
}

Stack注释中有这么一段话，告诉我们应该优先使用Deque接口及其实现。

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.

For example: Deque<Integer> stack = new ArrayDeque<Integer>();

在Java中，Stack类是基于Vector实现的，而Vector是一个线程安全的、可动态增长的数组。虽然Stack也是数组实现的，但由于Vector的一些内部机制（例如，每次增长时都会分配更大的数组，并将旧数组的内容复制到新数组中），它可能在某些操作上不如ArrayDeque高效。

相比之下，ArrayDeque是基于循环数组实现的，它避免了不必要的内存分配和复制操作。循环数组意味着当数组的一端达到容量限制时，元素会从另一端开始填充，从而充分利用了数组空间。这种实现方式通常比Vector或Stack更高效。

因此，即使Stack也是数组实现的，但由于Deque（如ArrayDeque）使用了不同的内部机制和优化，它在某些情况下可能会提供更好的性能。

另外，值得注意的是，在Java中，Stack类已经被标记为遗留（legacy），不建议在新的代码中使用。相反，应该使用Deque接口及其实现，如ArrayDeque，因为它们提供了更完整、更一致的操作集合，并且通常具有更好的性能。

性能

时间复杂度：push（数组赋值），empty为O(1)，pop与peek虽然涉及到移动数据，但只有在出栈为空的时候才执行，均摊后为O(1)。

空间复杂度为O(n)。

225.用队列实现栈

目标

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

输入：

["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]

输出：

[null, null, null, 2, 2, false]

解释：

MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

说明：

1 <= x <= 9
最多调用100 次 push、pop、top 和 empty
每次调用 pop 和 top 都保证栈不为空

进阶：你能否仅用一个队列来实现栈。

思路

这道题的目的是只使用标准库的部分API实现栈，即后进先出。

Java中可以使用Queue接口，offer插入队尾，peek获取队首元素，poll从队首获取并删除元素。

官网给出了两种方法，一种是使用两个队列，offer总是将新元素放到空队列q中，然后将另一队列q1从头至尾放入q，这样就实现了顺序的反转。

例如，依次入栈1，2，3，4：

说明：队首在右边

offer(1)：

q： 1

q1：
----------------------------
offer(2)：

q： 1

q1： 2

q1.offer(q.poll())：

q： 

q1： 1 2
----------------------------
offer(3)：

q： 3

q1： 1 2

while(!q1.isEmpty){q.offer(q1.poll())}：

q： 1 2 3

q1：
----------------------------
offer(4)：

q： 1 2 3

q1： 4

while(!q.isEmpty){q1.offer(q.poll())}：

q：

q1： 1 2 3 4

另一种只用一个队列的方法是：每次offer前先记录队列数据数量n，然后再offer，之后将前面n个数依次poll并offer到队尾。

例如，依次入栈1，2，3，4：

说明：队首在右边

offer(1)：

q： 1

----------------------------
n = 1

offer(2)：

q： 2 1

p.offer(p.poll())：

q： 1 2

----------------------------
n = 2

offer(3)：

q： 3 1 2

循环2次：p.offer(p.poll())

q： 1 2 3

----------------------------
n = 3

offer(4)：

q： 4 1 2 3

循环3次：p.offer(p.poll())

q：1 2 3 4

性能

这两种方法的性能基本相同。

时间复杂度：入栈操作均为O(n)，其余为O(1)。

空间复杂度：O(n)