标签： 数据结构

目标

给定一个整数数组 nums，处理以下类型的多个查询:

计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的 和 ，其中 left <= right

实现 NumArray 类：

• NumArray(int[] nums) 使用数组 nums 初始化对象
• int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的 总和 ，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + ... + nums[right] )

示例 1：

输入：
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出：
[null, 1, -1, -3]

解释：
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) 
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

说明：

• 1 <= nums.length <= 10^4
• -10^5 <= nums[i] <= 10^5
• 0 <= i <= j < nums.length
• 最多调用 104 次 sumRange 方法

思路

这个题看到之后没多想，提交之后发现和别人的性能差了10倍。这里的技巧就是提前将和计算的结果保存起来，用的时候直接用 prefix[right+1] - prefix[left] 即可。因为数组不可变所以这样是可行的。

这里没有使用 prefix[right] - prefix[left-1] 因为可以省去left为0的判断，不过多占用了4字节。其实没有必要纠结这些，真要计较的话，当left为0时还少了两次减法呢，并且cpu指令执行也有分支预测，无需关注这些细节。

代码

/**
 * @date 2024-03-18 8:36
 */
public class NumArray {

    private final int[] prefixSum;

    public NumArray(int[] nums) {
        prefixSum = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
    }

    public int sumRange(int left, int right) {
        return prefixSum[right + 1] - prefixSum[left];
    }

    public static void main(String[] args) {
        NumArray main = new NumArray(new int[]{-2, 0, 3, -5, 2, -1});
        System.out.println(main.sumRange(0, 2));
        System.out.println(main.sumRange(2, 5));
        System.out.println(main.sumRange(0, 5));
    }
}

性能

目标

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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)。

目标

请你仅使用两个队列实现一个后入先出（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)