题目描述

我们把无限数量 ∞ 的栈排成一行，按从左到右的次序从 0 开始编号。每个栈的的最大容量  capacity 都相同。

实现一个叫「餐盘」的类  DinnerPlates：

  • DinnerPlates(int capacity) - 给出栈的最大容量  capacity。
  • void push(int val) - 将给出的正整数  val  推入  从左往右第一个  没有满的栈。
  • int pop() - 返回  从右往左第一个  非空栈顶部的值，并将其从栈中删除；如果所有的栈都是空的，请返回  -1。
  • int popAtStack(int index) - 返回编号  index  的栈顶部的值，并将其从栈中删除；如果编号  index  的栈是空的，请返回 -1。

示例
略。(请点击链接查看原文。)

提示：

  • 1 <= capacity <= 20000
  • 1 <= val <= 20000
  • 0 <= index <= 100000
  • 最多会对 push，pop，和 popAtStack 进行 200000 次调用。

来源：LeetCode

思路

这题乍一看没什么难度，如果直接根据题意写的话，很容易。但是那样会超时，测试用例给的压力很大，目的也在于要求我们要以更高效的方法解决此题。
我的解法是，在DinnerPlates增加两个字段，为下次push还有pop的下标。然后下次有操作就可以直接从下标获取对应的栈，从而免去了重复的遍历过程，提高效率。
具体维护过程简述：

  1. 每次push时，直接根据pushIndex去压入。若此位置还没有栈，创建一个栈，压入，而且此时popIndex也应该指到此处。压入完成后，还需要判断该栈是否已经满了，若满了需要将pushIndex移动到后面第一个未满的位置。
  2. 每次pop时，直接从popIndex出弹出，然后判断此栈是否已空，空了则应该把popIndex向左移动到第一个非空位置。
  3. 在指定栈弹出时，若指定栈位置等于popIndex，则化归到第 2 条。若在popIndex之前，则直接弹出此栈。然后index若在pushIndex之前，则应该把pushIndex提前到index处。

解法

/**
 * @param {number} capacity
 */
function DinnerPlates(capacity) {
  this.stacks = [];
  this.capacity = capacity;
  this.pushIndex = 0;
  this.popIndex = 0;
}

/**
 * @param {number} val
 * @return {void}
 */
DinnerPlates.prototype.push = function(val) {
  if (!this.stacks[this.pushIndex]) {
    this.stacks[this.pushIndex] = [];
    this.popIndex = this.pushIndex;
  }

  this.stacks[this.pushIndex].push(val);
  this.pushIndex;

  // 若满了，移动到下一个
  while (this.stacks[this.pushIndex] && this.stacks[this.pushIndex].length === this.capacity) {
    this.pushIndex++;
  }
};

/**
 * @return {number}
 */
DinnerPlates.prototype.pop = function() {
  const result = this.stacks[this.popIndex].pop();

  // 若空了，移动到前一个
  while (this.stacks[this.popIndex].length === 0 && this.popIndex > 0) {
    this.popIndex--;
  }

  return result || -1;
};

/**
 * @param {number} index
 * @return {number}
 */
DinnerPlates.prototype.popAtStack = function(index) {
  if (index >= this.stacks.length) {
    return -1;
  }

  if (index === this.popIndex) {
    return this.pop();
  }

  const result = this.stacks[index].pop();

  if (this.pushIndex > index) {
    this.pushIndex = index;
  }

  return result || -1;
};

/**
 * Your DinnerPlates object will be instantiated and called as such:
 * var obj = new DinnerPlates(capacity)
 * obj.push(val)
 * var param_2 = obj.pop()
 * var param_3 = obj.popAtStack(index)
 */
Last Updated:
Contributors: henri.zhang