【Day 3 】2024-04-10 - 1381. 设计一个支持增量操作的栈

[azl397985856]

1381. 设计一个支持增量操作的栈

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/design-a-stack-with-increment-operation/

前置知识

• 栈
• 前缀和

  题目描述

  
  请你设计一个支持下述操作的栈。

实现自定义栈类 CustomStack ：

CustomStack(int maxSize)：用 maxSize 初始化对象，maxSize 是栈中最多能容纳的元素数量，栈在增长到 maxSize 之后则不支持 push 操作。 void push(int x)：如果栈还未增长到 maxSize ，就将 x 添加到栈顶。 int pop()：弹出栈顶元素，并返回栈顶的值，或栈为空时返回 -1 。 void inc(int k, int val)：栈底的 k 个元素的值都增加 val 。如果栈中元素总数小于 k ，则栈中的所有元素都增加 val 。

示例：

输入： ["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"] [[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]] 输出： [null,null,null,2,null,null,null,null,null,103,202,201,-1] 解释： CustomStack customStack = new CustomStack(3); // 栈是空的 [] customStack.push(1); // 栈变为 [1] customStack.push(2); // 栈变为 [1, 2] customStack.pop(); // 返回 2 --> 返回栈顶值 2，栈变为 [1] customStack.push(2); // 栈变为 [1, 2] customStack.push(3); // 栈变为 [1, 2, 3] customStack.push(4); // 栈仍然是 [1, 2, 3]，不能添加其他元素使栈大小变为 4 customStack.increment(5, 100); // 栈变为 [101, 102, 103] customStack.increment(2, 100); // 栈变为 [201, 202, 103] customStack.pop(); // 返回 103 --> 返回栈顶值 103，栈变为 [201, 202] customStack.pop(); // 返回 202 --> 返回栈顶值 202，栈变为 [201] customStack.pop(); // 返回 201 --> 返回栈顶值 201，栈变为 [] customStack.pop(); // 返回 -1 --> 栈为空，返回 -1

提示：

1 <= maxSize <= 1000 1 <= x <= 1000 1 <= k <= 1000 0 <= val <= 100 每种方法 increment，push 以及 pop 分别最多调用 1000 次

[Dtjk]

class CustomStack {
public:
    int ssize;
    stack<int> ss;
    CustomStack(int maxSize) {
        ssize = maxSize;
    }

    void push(int x) {
        if (ss.size() < ssize) ss.push(x);
    }

    int pop() {
         if(!ss.empty()) {
            int res = ss.top();
            ss.pop();
            return res;
         }
         else return -1;
    }

    void increment(int k, int val) {
         stack<int> ss2;
         while (!ss.empty()){
            ss2.push(ss.top());
            ss.pop();
         }
         int sum = 0;
         while(!ss2.empty()){
            sum++;
            if (sum <= k) ss.push(ss2.top() + val);
            else ss.push(ss2.top());
            ss2.pop();
         }
    }
};

[CathyShang]

思路：

• 看到前k个增添一个增量，用数组实现。
• 优化前，增添函数中for循环求和更新栈中元素，时间复杂度为$O(N)$ N=k
• 前缀和优化，
  • 增添函数更新增量数组，举例中，"increment","increment", 对应 "add[2]=100","add[1]=100"，其记录前k（k<top）个增量值val，
  • 在pop()，通过stk[top]+add[top]获取增量后元素，并通过add[top-1] += add[top];更新增量数组。

代码：

class CustomStack {
public:
    vector<int> stk, add;
    int top;

    CustomStack(int maxSize) {
        stk.resize(maxSize);
        add.resize(maxSize);
        top = -1; //没满栈,监测栈顶位置
    }

    void push(int x) {
        if(top != stk.size()-1){ //错误 if(top < stk.size()-1)
            ++top;
            stk[top] = x;
            // std::cout << 'test';
        }
        // std::cout << top <<'\n';
    }

    int pop() {
        int cur;
        if(top==-1) return -1; //空了
        cur = stk[top] + add[top];
        if(top != 0) add[top-1] += add[top]; // 错误 add[top-1] = add[top]
        add[top] = 0; //跟着元素出栈清零
        --top;
        return cur; 
    }

    void increment(int k, int val) {
        int rag;
        rag = min(k, top+1);
        // 优化器前
        // for(int i = 0; i<rag; ++i){
        //     stk[i] += val;
        // }
        if( rag >= 1) add[rag-1] += val;
    }
};

复杂度：

• 时间复杂度： push，pop，increment $O(1)$
• 空间复杂度：$O(N)$ 使用两个长度为N=maxSize的数组

[coderXiaowq]

Java 思路: 底层创建一个数组用于存储数据,并定义一个变量保存数组中的有效元素个数

class CustomStack {
    private int[] a;// 底层数组 保存数据
    private int N;// 数组逻辑长度

    public CustomStack(int maxSize) {// maxSize>=1
        a = new int[maxSize];
    }

    public void push(int x) {
        if (N == a.length)
            return;
        a[N++] = x;
    }

    public int pop() {
        if (N == 0)
            return -1;
        return a[--N];
    }

    public void increment(int k, int val) {// k>=1
        if (k >= N) {
            for (int i = 0; i < N; i++) {
                a[i] += val;
            }
        } else {
            for (int i = 0; i < k; i++) {
                a[i] += val;
            }
        }
    }
}

[xil324]

/**
 * @param {number} maxSize
 */
var CustomStack = function(maxSize) {
    this.maxSize = maxSize; 
    this.stack = []; 
};

/** 
 * @param {number} x
 * @return {void}
 */
CustomStack.prototype.push = function(x) {
    if(this.stack.length === this.maxSize) return; 
    this.stack.push(x); 
};

/**
 * @return {number}
 */
CustomStack.prototype.pop = function() {
    if(this.stack.length === 0) return -1;
    return this.stack.pop(); 
};

/** 
 * @param {number} k 
 * @param {number} val
 * @return {void}
 */
CustomStack.prototype.increment = function(k, val) {
    console.log(k, this.stack)
    for (let i=0; i < k; i++) {
        if(i < this.stack.length) {
            this.stack[i] += val
        }
    }
};

time complexity: push: O(1) pop: O(1) increment O(k) space complexity: O(n) n = maxSize

[RocJeMaintiendrai]

思路

额外创建一个数组int[] inc来记录对应的index上增加的值，index = Math.min(k, stack.size()) - 1。 当pop操作时，将pop出的值与inc[i]的值相加返回，inc[i-1]的值要加上inc[i]的值，之后inc[i]变为0.

代码

class CustomStack { int n; int[] inc; Stack stack;

public CustomStack(int maxSize) {
    n = maxSize;
    inc = new int[n];
    stack = new Stack<>();
}

public void push(int x) {
    if(stack.size() < n) {
        stack.push(x);
    }
}

public int pop() {
    int i = stack.size() - 1;
    if(i < 0) {
        return -1;
    }
    if(i > 0) {
        inc[i - 1] += inc[i];
    }
    int res = stack.pop() + inc[i];
    inc[i] = 0;
    return res;
}

public void increment(int k, int val) {
    int i = Math.min(k, stack.size()) - 1;
    if(i >= 0) {
        inc[i] += val;
    }
}

}

**复杂度分析**
- 时间复杂度：所有操作均为O(1)
- 空间复杂度：开了新的数组所以为O(N)

[Alexzhang-Mini]

class CustomStack:

    def __init__(self, maxSize: int):
        self.maxSize = maxSize
        self.stack = []

    def push(self, x: int) -> None:
        if len(self.stack) < self.maxSize:
            self.stack.append(x)

    def pop(self) -> int:
         if self.stack:
            return self.stack.pop()
         else:
            return -1  

    def increment(self, k: int, val: int) -> None:
        for i in range(min(k, len(self.stack))):
            self.stack[i] += val

[Junru281]

Cool. 时隔半年再做, 终于可以很快做出来了.

class CustomStack:
    def __init__(self, maxSize: int):
        self.maxSize = maxSize
        self.array = []

    def push(self, x: int) -> None:
        if len(self.array) < self.maxSize:
            self.array.append(x)

    def pop(self) -> int:
        if len(self.array) == 0:
            return -1
        else:
            return self.array.pop()

    def increment(self, k: int, val: int) -> None:
        for i in range(min(k, len(self.array))):
            self.array[i] += val

# Your CustomStack object will be instantiated and called as such:
# obj = CustomStack(maxSize)
# obj.push(x)
# param_2 = obj.pop()
# obj.increment(k,val)

[zhiyuanpeng]

class CustomStack:

    def __init__(self, maxSize: int):
        self.stack = []
        self.size = 0
        self.maxSize = maxSize
        self.add = []

    def push(self, x: int) -> None:
        if self.size < self.maxSize:
            self.stack.append(x)
            self.size += 1
            self.add.append(0)

    def pop(self) -> int:
        if self.size > 0:
            self.size -= 1
            inc = self.add.pop()
            if self.size > 0:
                self.add[-1] += inc
            val = self.stack.pop()
            return val+inc
        return -1

    def increment(self, k: int, val: int) -> None:
        n = min(k, self.size)
        if n >= 1:
            self.add[n-1] += val

time: push O(1), pop O(1), increment O(1), space O(N)

[jinzhepro]

题解

/**
 * @param {number} maxSize
 */
var CustomStack = function(maxSize) {
  this.stack = []
  this.length  = maxSize
};

/**
 * @param {number} x
 * @return {void}
 */
CustomStack.prototype.push = function(x) {
  if(this.stack.length !== this.length){
    this.stack.push(x);
  }

};

/**
 * @return {number}
 */
CustomStack.prototype.pop = function() {
  if(this.stack.length === 0) return -1
  return this.stack.pop();
};

/**
 * @param {number} k
 * @param {number} val
 * @return {void}
 */
CustomStack.prototype.increment = function(k, val) {
  const l =  k  > this.stack.length ? this.stack.length : k
  for(let i = 0; i < l; i++) {
    this.stack[i] += val
  }
};

复杂度

时间复杂度：push、pop O(1) increment O(n) 空间复杂度：push、pop O(1) increment O(n)

[atom-set]

思路

• 栈的结构特性: 先进先出，只能从一端进栈和出栈
• 自定义栈类的要求:
  • 限制了栈的长度，栈满了就不允许进栈
  • 新增了 inc 操作

可以借助数组数据结构模拟栈，进栈调用 push API，出栈调用 pop API。进栈的时候判断数组长度是不是大于 maxSize， 出栈的时候判断数组长度是否为 0

代码

/**
 * @param {number} maxSize
 */
var CustomStack = function (maxSize) {
  this.maxSize = maxSize;
  this.stack = [];
};

/**
 * @param {number} x
 * @return {void}
 */
CustomStack.prototype.push = function (x) {
  if (this.stack.length < this.maxSize) {
    this.stack.push(x);
  }
  return null;
};

/**
 * @return {number}
 */
CustomStack.prototype.pop = function () {
  if (this.stack.length > 0) {
    return this.stack.pop();
  }
  return -1;
};

/**
 * @param {number} k
 * @param {number} val
 * @return {void}
 */
CustomStack.prototype.increment = function (k, val) {
  var temp = [];
  for (let i = 0; i < k; i++) {
    if (this.stack.length > 0) {
      temp.push(this.stack.shift());
    }
  }

  while (temp.length > 0) {
    const v = temp.pop();
    this.stack.unshift(v + val);
  }
  return null;
};
...

复杂度分析

• 时间复杂度
  • 初始化（构造函数）: O(1)
  • push: O(1)
  • pop: O(1)
  • inc: O(k)
• 空间复杂度：O(maxSize) [这里用到了一个长度为 maxSize 的数组作为辅助空间]

[hillsonziqiu]

思路

通过数组来模拟栈。通过push和pop来操作栈。CustomStack有两个属性一个是list，一个是maxSize； increment的实现： 遍历长度判断 const len = this.list.length > k ? k : this.list.length; 如果栈长度大于k，那么就遍历到k，如果长度小于k，那么遍历整个list即可；

题解

/*
 * @lc app=leetcode.cn id=1381 lang=javascript
 *
 * [1381] 设计一个支持增量操作的栈
 */

// @lc code=start
/**
 * @param {number} maxSize
 */
var CustomStack = function (maxSize) {
  const list = [];
  //   list.length = maxSize;
  this.maxSize = maxSize;
  this.list = list;
};

/**
 * @param {number} x
 * @return {void}
 */
CustomStack.prototype.push = function (x) {
  if (this.list.length >= this.maxSize) {
    return;
  }
  this.list.push(x);
};

/**
 * @return {number}
 */
CustomStack.prototype.pop = function () {
  if (this.list.length <= 0) {
    return -1;
  }
  return this.list.pop();
};

/**
 * @param {number} k
 * @param {number} val
 * @return {void}
 */
CustomStack.prototype.increment = function (k, val) {
  const len = this.list.length > k ? k : this.list.length;
  for (let i = 0; i < len; i++) {
    this.list[i] += val;
  }
};

/**
 * Your CustomStack object will be instantiated and called as such:
 * var obj = new CustomStack(maxSize)
 * obj.push(x)
 * var param_2 = obj.pop()
 * obj.increment(k,val)
 */
// @lc code=end

复杂度分析

时间复杂度:

• CustomStack O(1)
• push O(1)
• pop O(1)
• increment O(n) 空间复杂度: O（N） N就是maxSize;

[wwz223]

class CustomStack {
  constructor(maxSize) {
    this.maxSize = maxSize;
  }
  /**
   * 最大值
   * @param {number} maxSize
   */
  maxSize = 0;
  /**
   * 栈空间
   */
  stack = [];
  /**
   * 初始化
   * @param {number} maxSize
   */
  /**
   * 入栈
   * @param {number} maxSize
   * @return {void}
   */
  push(x) {
    if (this.stack.length < this.maxSize) this.stack.push(x);
    return null;
  }
  /**
   * 出栈
   * @param {number} x
   * @return {number}
   */
  pop(x) {
    if (this.stack.length > 0) return this.stack.pop();
    return -1;
  }
  /**
   * 增加值操作
   * @param {number} k
   * @param {number} val
   */
  increment(k, val) {
    for (let i = 0; i < k && i < this.stack.length; i++) {
      this.stack[i] += val;
    }
    return null;
  }
}

// 输入：
const action = ['CustomStack', 'push', 'push', 'pop', 'push', 'push', 'push', 'increment', 'increment', 'pop', 'pop', 'pop', 'pop'];
const param = [[3], [1], [2], [], [2], [3], [4], [5, 100], [2, 100], [], [], [], []];

const run = (action, param) => {
  let stack = null;
  let result = [];
  let res = null;
  action.map((a, i) => {
    if (a === 'CustomStack') {
      stack = new CustomStack(...param[i]);
      res = null;
    } else {
      res = stack[a](...param[i]);
    }

    result.push(res);
  });
  return result;
};

console.log(run(action, param));

复杂度分析

时间复杂度： push、pop: O(1) increment：O(k) 空间复杂度：O(maxsize)

[GReyQT]

题解思路：

（1）使用vector容器作为数据的载体 （2）vector的末尾作为栈顶

代码：

class CustomStack {
private:
    int _size;
    int _maxsize;
    vector<int> stack;

public:
    CustomStack(int maxSize) {
        _maxsize=maxSize;
        _size=0;
    }

    void push(int x) {
        if(_size < _maxsize)
        {
            stack.push_back(x);
            _size++;
        }            
    }

    int pop() {
        if(0 == stack.size())
            return -1;

        int re = stack.back();

        stack.pop_back();
        _size--;                   

        return re;
    }

    void increment(int k, int val) {
        if(k > stack.size())
            k=stack.size();

        int count=0;
        for(auto it = stack.begin(); it != stack.end(); ++it)
        {
            if(count == k)
                break;

            *it += val;
            count++;
        }
    }
};

复杂度分析： CustomStack(int maxSize)：

• 时间复杂度：不依赖于输入，所以为O(1)
• 空间复杂度：不依赖于输入，所以为O(1)

void push(int x)：

• 时间复杂度：push_back() 操作的平均时间复杂度是 O(1)，因此平均时间复杂度为O(1)，偶尔需要重新分配内存，导致复杂度为 O(n)
• 空间复杂度：push_back() 操作的空间时间复杂度是 O(1)，因此平均空间复杂度为O(1)，偶尔需要重新分配内存，导致复杂度为 O(n)

int pop()：

• 时间复杂度：不涉及对内存的操作，只需要减少vector向量的计数，所以为O(1)
• 空间复杂度：不需要额外的内存分配或释放，所以为O(1)

void increment(int k, int val)：

• 时间复杂度：时间复杂度取决于输入的int k，因此为O(k)
• 空间复杂度：没有使用额外的空间，所以为O(1)

[Hawkins-hjq]

思路

数组实现栈

代码

class CustomStack {
    // 声明一个数组，作为自定义栈的底层实现
    int[] stackArray;
    // 栈顶位置监控
    int pos = 0;

    public CustomStack(int maxSize) {
        stackArray = new int[maxSize];
    }

    public void push(int x) {
        // 栈空间满了，不能入栈
        if(pos==stackArray.length){
            return;
        }
        // 入栈
        stackArray[pos++]=x;
    }

    public int pop() {
        if(pos==0){
            return -1;
        }
        return stackArray[--pos];

    }

    public void increment(int k, int val) {
        // 栈中元素个数小于k
        if(k>stackArray.length){
            for(int i = 0;i<stackArray.length;i++){
                stackArray[i] += val;
            }
        } else{
              // 栈中元素个数小于k
            for(int j =0;j<k;j++){
                    stackArray[j] += val;
                }
        }
    }
}

复杂度

时间复杂度： push、pop: O(1),increment:O(K) 空间复杂度：O(maxSize)

[Martina001]

补打卡 class CustomStack { // 1。 直接使用双栈比较直接，就是保存一个元素总和，当递增的时候用备用栈倒出来，从倒到n-k的时候开始增加，然后再倒回去原来的栈

// 2。 其实这道题考察的是模拟的思想，用数组表示栈，会更直接一点，每次incre就遍历0-k对数组执行++就行，这样incre的复杂度是Ok

// 3。 有一个比较巧妙的方法就是使用前缀和数组的思想，用数组实现栈，保存一个addArr[i]表示在i位置需增加的值，这样每次increment只用增加addArr[k]位置的值
// push保存一个栈顶索引，topIndex，pop的时候需要拿到stack[topIndex]+addArr[topIndex]的值
// 又因为每次incre的时候只是增加了addArr[k],为了保证每次取到的值都是已经被加过的，所以每次pop以后，addArr[topIndex-1]位置也要增加addArr[topIndex]
// 这样看似有点难理解，但是想清楚了就很妙了，可以保证incre的时候复杂度都是O1

int [] stack;
int addArr[];

int topIndex;

// 直接写一下前缀和方式
public CustomStack(int maxSize) {
    addArr = new int[maxSize];
    stack = new int[maxSize];
    topIndex = -1;
}

public void push(int x) {
    if(topIndex == stack.length-1){
        return ;
    }
    stack[++topIndex] = x;
}

public int pop() {
    if(topIndex==-1){
        return -1;
    }

    int addVal = addArr[topIndex];
    int res = stack[topIndex]+addVal;

    // 更新最新top索引处的add值
    if(topIndex>=1){
        addArr[topIndex-1] += addVal;
    }
    // 记得还原addArr[topIndex] =0
    addArr[topIndex] =0;
    topIndex--;
    return res;
}

public void increment(int k, int val) {
    // 这里要用topIndex和K比较
    int actualK = Math.min(k,topIndex+1);
    if(actualK >=1){
        addArr[actualK-1] +=val;
    }
}

}

/**

• Your CustomStack object will be instantiated and called as such:
• CustomStack obj = new CustomStack(maxSize);
• obj.push(x);
• int param_2 = obj.pop();
• obj.increment(k,val); */ //leetcode submit region end(Prohibit modification and deletion)

}

[YANGLimbo]

class CustomStack {
protected:
    vector<int> m_customStack;
    int m_pos = -1;
    int m_maxSize = 1;
public:
    CustomStack(int maxSize):m_customStack(maxSize),m_maxSize(maxSize) {
    }

    void push(int x) {
        if(m_pos < m_maxSize - 1){
            m_pos ++;
            m_customStack[m_pos] = x;
        }
    }

    int pop() {
        if(m_pos == -1){
            return -1;
        }
        m_pos --;
        return m_customStack[m_pos + 1];
    }

    void increment(int k, int val) {
        int increNum = 0;
        if(m_pos + 1 < k ){
            increNum = m_pos + 1;
        }else{
            increNum = k;
        }
        for(int i = 0;i < increNum;i++){
            m_customStack[i] += val;
        }
    }
};

[borderGong]

代码

class CustomStack {
    private maxSize: number;
    private stack: number[];
    private incMap: any;
    constructor(maxSize) {
        this.maxSize = maxSize;
        this.stack = [];
        this.incMap = {}; // 用于记录增量操作
    }

    push(x) {
        if (this.stack.length < this.maxSize) {
            this.stack.push(x);
        }
    }

    pop() {
        if (this.stack.length === 0) {
            return -1;
        }
        // 处理增量操作
        let inc = this.incMap[this.stack.length] || 0;
        if (this.stack.length > 1) {
            this.incMap[this.stack.length - 1] = (this.incMap[this.stack.length - 1] || 0) + inc;
        }
        return this.stack.pop() + inc;
    }

    increment(k, val) {
        const top = Math.min(k, this.stack.length);
        this.incMap[top] = (this.incMap[top] || 0) + val;
    }
}

时间复杂度

• push O(1)
• pop O(1)
• increment O(n)

思路

用数组模拟栈

[pandapls]

var CustomStack = function(maxSize) { this.stack = []; this.maxSize = maxSize };

/**

• @param {number} x
• @return {void} */ CustomStack.prototype.push = function(x) { if (this.stack.length >= this.maxSize) { return; } this.stack.push(Number(x)); };

/**

• @return {number} */ CustomStack.prototype.pop = function() { if (this.stack.length === 0) { return -1 }

  return this.stack.pop() };

/**

• @param {number} k
• @param {number} val
• @return {void} */ CustomStack.prototype.increment = function(k, val) { for(let i = 0; i < k && i < this.stack.length; i++) { this.stack[i] = this.stack[i] + val } return this.stack };

• 时间复杂度：O(N)
• 空间复杂度：O(1)