LeetCode 面试题 03.03. 堆盘子

一、题目

  堆盘子。设想有一堆盘子，堆太高可能会倒下来。因此，在现实生活中，盘子堆到一定高度时，我们就会另外堆一堆盘子。请实现数据结构 SetOfStacks，模拟这种行为。SetOfStacks 应该由多个栈组成，并且在前一个栈填满时新建一个栈。此外，SetOfStacks.push() 和 SetOfStacks.pop() 应该与普通栈的操作方法相同（也就是说，pop()返回的值，应该跟只有一个栈时的情况一样）。 进阶：实现一个 popAt(int index) 方法，根据指定的子栈，执行pop操作。

  当某个栈为空时，应当删除该栈。当栈中没有元素或不存在该栈时，pop，popAt 应返回 -1.

  点击此处跳转题目。

示例1:

输入：
[“StackOfPlates”, “push”, “push”, “popAt”, “pop”, “pop”]
[[1], [1], [2], [1], [], []]
输出：
[null, null, null, 2, 1, -1]

示例2:

输入：
[“StackOfPlates”, “push”, “push”, “push”, “popAt”, “popAt”, “popAt”]
[[2], [1], [2], [3], [0], [0], [0]]
输出：
[null, null, null, null, 2, 1, 3]

二、C# 题解

  这题不难，但是很繁琐。尤其是题目没有说明清楚，不仅不给出数据规模，而且还会出现栈的大小为 0 的情况，真是绷不住了。当中间栈有元素弹出时，后面的元素并不前移，这点题目也没说，也是挺离谱的。

public class StackOfPlates {private class Node {public int val = 0; // 若作为头结点，则表示该链表串联的元素个数public Node next = null;public Node(int v, Node n) {val = v;next = n;}}private Node[] stack;                   // 头结点数组，每个结点连接一个链表，表示一个栈private int MAX_CAP, p = -1;            // MAX_CAP 表示每个栈最多有几个盘子，p 用于指向当前栈private static int MAX_STACK_NUM = 999; // 栈的最大个数public StackOfPlates(int cap) {MAX_CAP = cap;stack = new Node[MAX_STACK_NUM];}public void Push(int val) {// 前置判断条件：不给放盘子或者栈达到最大个数if (MAX_CAP == 0 || p == MAX_STACK_NUM - 1 && stack[p].val == MAX_CAP) return; // 如果 p 为 -1 或当前栈满，则激活新栈if (p == -1 || stack[p].val == MAX_CAP) stack[++p] = new Node(0, null); // 压入元素stack[p].next = new Node(val, stack[p].next);stack[p].val++;}public int Pop() {// 前置判断条件：不给放盘子或者没有栈if (MAX_CAP == 0 || p == -1) return -1; // 弹出元素int result = stack[p].next.val;stack[p].next = stack[p].next.next;stack[p].val--;// 如果当前栈满，则指针前移if (stack[p].val == 0) stack[p--] = null;return result;}public int PopAt(int index) {// 前置判断条件：不给放盘子或没有栈if (MAX_CAP == 0 || stack[index] == null) return -1;// 弹出元素int result = stack[index].next.val;stack[index].next = stack[index].next.next;stack[index].val--;// 移除后栈为空，则将后面的栈前移if (stack[index].val == 0) {for (int i = index; i < p; i++) {stack[i].next = stack[i + 1].next;stack[i].val = stack[i + 1].val;stack[i + 1].next = null;}stack[p--] = null;}return result;}
}/*** Your StackOfPlates object will be instantiated and called as such:* StackOfPlates obj = new StackOfPlates(cap);* obj.Push(val);* int param_2 = obj.Pop();* int param_3 = obj.PopAt(index);*/

• 时间复杂度：$O(1)$。
• 空间复杂度：$O(n)$。