【Day 3 】2024-12-03 - 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 次

[shangjiaw]

class CustomStack: def init(self, maxSize): self.stack = [] self.size = 0 self.maxSize = maxSize

def push(self, x):
    if self.size < self.maxSize:
        self.stack.append(x)
        self.size += 1
    else:
        print("reach max size. cannot push.")

def pop(self):
    if self.stack:
        self.size -= 1
        return self.stack.pop(-1)
    else:
        return -1

def increment(self, k, val):
    if self.size < k:
        for i in range(self.size):
            self.stack[i] += val
    else:
        for i in range(k):
            self.stack[i] += val

customStack = CustomStack(3) customStack.push(1) #栈变为 [1] customStack.push(2) #栈变为 [1, 2] print(customStack.pop()) #返回栈顶值 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] print(customStack.pop()) #返回 103 --> 返回栈顶值 103，栈变为 [201, 202] print(customStack.pop()) #返回 202 --> 返回栈顶值 202，栈变为 [201] print(customStack.pop()) #返回 201 --> 返回栈顶值 201，栈变为 [] print(customStack.pop()) #返回 -1 --> 栈为空，返回 -1

[hebingliang]

/**

• @param {number} maxSize */ var CustomStack = function(maxSize) { arr = []; maxLength = maxSize; };

/**

• @param {number} x
• @return {void} */ CustomStack.prototype.push = function(x) { if(arr.length==maxLength){ console.error("已经超出了") }else{ arr.push(x) } };

/**

• @return {number} */ CustomStack.prototype.pop = function() { if(arr.length){ let num = arr[arr.length-1] arr.splice(arr.length-1,1); return num; }else{ return -1 } };

/**

• @param {number} k
• @param {number} val
• @return {void} */ CustomStack.prototype.increment = function(k, val) { for(let i = 0;i<(k>arr.length?arr.length:k);i++){ arr[i] = arr[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) */

[QunShanHe]

class CustomStack:

def __init__(self, maxSize: int):
   self.top = -1
   self.stack = [0] * maxSize
   self.maxSize = maxSize

def push(self, x: int) -> None:
    if self.top < self.maxSize-1:
        self.stack[self.top+1] = x
        self.top = self.top+1

def pop(self) -> int:
    if self.top > -1:
        self.top = self.top-1
        return self.stack[self.top+1]
    else:
        return -1

def increment(self, k: int, val: int) -> None:
    lim = min(k,self.top+1)
    for i in range(lim):
        self.stack[i] = self.stack[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)

[tuuna]

include

class CustomStack { private: std::vector stack; int maxSize;

public: CustomStack(int maxSize) { this->maxSize = maxSize; }

void push(int x) {
    if (stack.size() < maxSize) {
        stack.push_back(x);
    }
}

int pop() {
    if (!stack.empty()) {
        int top = stack.back();
        stack.pop_back();
        return top;
    } else {
        return -1;
    }
}

void increment(int k, int val) {
    for (int i = 0; i < k && i < stack.size(); i++) {
        stack[i] += val;
    }
}

};

[laurallalala]

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 len(self.stack) <= 0:
            return -1
        return self.stack.pop()

    def increment(self, k: int, val: int) -> None:
        n = len(self.stack)
        tmpStack = []
        while len(self.stack) > k:
            tmpStack.append(self.stack.pop())
        while len(self.stack) > 0:
            tmpStack.append(self.stack.pop()+val)
        while tmpStack:
            self.stack.append(tmpStack.pop())

[tongxw]

class CustomStack {
    Deque<Integer> stack; // SC O(n)
    int maxSize;

    // 用增量数数组记录增量，出栈时加到栈顶元素
    int[] incr; // SC O(n)

    public CustomStack(int maxSize) {
        this.stack = new LinkedList<>();
        this.maxSize = maxSize;
        incr = new int[maxSize + 1];
    }

    public void push(int x) {
        if (stack.size() == maxSize) {
            return;
        }

        stack.push(x); // TC O(1)

    }

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

        // stack内容如下:
        // [va1, val2, val3, val4]
        //  ^                 ^
        // bottom             top

        // incr数组内容如下:
        // [ 0,  0,   incr_val, 0]
        //   ^           ^
        // not_used    incr[2] = incr_val，代表stack底部的2个元素都会增加incr_val

        int top = stack.pop();
        int incr_val = incr[size];

        if (incr_val != 0) {
            top += incr_val;

            incr[size - 1] += incr_val;
            incr[size] = 0;
        }

        return top; // TC O(1)
    }

    public void increment(int k, int val) { // TC O(1)
        int total = Math.min(k, stack.size());
        incr[total] += 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);
 */

[HaodongWang1995]

思路

1. 设置maxSize： a. 创建时记录 b. push 时检查当前大小是否小于等于maxSize，大于直接返回
2. push 功能 a. 新增元素
3. pop功能 a. 删除元素
4. inc 功能 a. 判断输入个数是否小于等于当前数量，大于直接返回 b. 从底开始根据入参依次相加

代码

/**
 */
/**
 * @param {number} maxSize
 */
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(x)
};

/**
 * @return {number}
 */
CustomStack.prototype.pop = function() {
    let a = this.stack.pop()
    return a || -1
};

/** 
 * @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] +=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)
 */

复杂度分析

时间复杂度 O(1)

空间复杂度 O(n)

总结

在创建数组的时候如果用 new Array() 方法会导致长度固定，如果后变要用到 length 属性需要考虑到位

[baiqz]

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

1、问题

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

实现自定义栈类 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 次

2、思路

初始化栈，有储存元素列表、当前元素数量、最大容量和一个随出入栈动态变化的元素增量列表。

然后实现入栈操作：判断栈的容量是否已满，当前数量小于最大容量

实现出栈操作：判断栈是否为空，当前数量是否为0，为0返回-1，判断目前数量是否至少有2个元素，如果有则把倒数第一的增量加到倒数第二上，然后再删除末尾元素和末尾增量值并返回末尾元素的值与增量表末尾的增量之和。

实现增量操作：判断容量是否为空，若不为空，进行增量操作，为使增量范围不超过当前元素数量，在要增量的前个k元素的k值和当前元素数量之间取最小值，并-1得到索引求增量对应位置的目前增量值，再与新加入的要求前k数增量Val求和。

3、代码

class CustomStack():
  def __init__(self, size: int):
      self.st = []
      self.cnt = 0
      self.size = size
      self.incrementals = []

  def push(self, x:int) -> None:
      if self.cnt < self.size:
          self.st.append(x)
          self.incrementals.append(0)
          self.cnt += 1

  def pop(self)-> int:
      if self.cnt == 0: return -1
      self.cnt -= 1
      if self.cnt >= 1:
         self.incrementals[-2] += self.incrementals[-1]
      return self.st.pop() + self.incrementals.pop()

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

4、复杂度

1. 增量值列表动态调整: 我们不再使用一个固定大小为 maxSize 的 incrementals 数组，而是使用一个动态的列表，它的大小始终与当前栈的长度保持一致。
2. 入栈和出栈同步操作: 每次执行 push 操作时，我们同时将一个新的增量值 0 入栈到 incrementals 列表中。类似地，每次执行 pop 操作时，我们也会将增量值与栈顶元素一起出栈。这样就保证了 incrementals 列表始终与栈元素保持一致。
3. 空间复杂度降低: 通过这种优化，我们避免了使用一个大小为 maxSize 的固定数组，将空间复杂度从 O(maxSize) 降低到了 O(n)，其中 n 是当前栈的长度。

5、总结

还是没写出来代码，跟着讲义和答案解析，自己尝试理解代码逻辑，背会默写。

[Master-guang]

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

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

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

/**
 * @param {number} k
 * @param {number} val
 * @return {void}
 */
CustomStack.prototype.increment = function (k, val) {
  let len = this.res.length;
  if (len < k) {
    this.res = this.res.map((item) => (item += val));
  } else {
    let arr = this.res.splice(0, k);
    this.newArr = arr.map((item) => (item += val));
    this.res = [...this.newArr, ...this.res];
  }

};

/**
 * 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)
 */

[XiaogaoDDD]

typedef struct {
    int *data; //数据域
    int top; //栈顶指针
    int capcaity; //表示栈的最大容量
} CustomStack;

CustomStack* customStackCreate(int capcaity) {
     CustomStack* stack = (CustomStack*)malloc(sizeof(CustomStack));
    stack->data = (int*)malloc(sizeof(int) * capcaity);
    stack->capcaity = capcaity;
    stack->top = -1; //栈顶指针始终指向栈顶的元素，将其先初始化为-1
    return stack;
}

void customStackPush(CustomStack* obj, int x) {
    if (obj->top == obj->capcaity - 1) {
        return;
        }
    obj->data[++obj->top] = x;//判断当前元素的个数是否达到上限，如果没有达到，就把 top 后移一个位置并添加一个元素。
}

int customStackPop(CustomStack* obj) {
    if (obj->top == -1) {
        return -1;
    }
    return obj->data[obj->top--];//非空返回栈顶元素并将 top 前移一位
}

void customStackIncrement(CustomStack* obj, int k, int val) {
     if (obj->top + 1 < k) {
        for (int i = 0; i <= obj->top; i++) { 
            //注意这里需要小于等于，此时栈顶指向的位置是栈顶的元素
            obj->data[i] += val;
        }
    }else {
        for (int i = 0; i < k; i++) {
            obj->data[i] += val;
        }
    }
}

void customStackFree(CustomStack* obj) {
    free(obj->data);
    free(obj);//释放
}

[lxy12L]

class CustomStack(object):

def __init__(self, maxSize):

    self.stack=[]
    self.maxSize=maxSize

def push(self, x):

    if len(self.stack)<self.maxSize:
        self.stack.append(x)

def pop(self):

    if len(self.stack)>0:
       return self.stack.pop()
    else:
        return -1

def increment(self, k, val):

    for i in range(min(k,len(self.stack))):
        self.stack[i] += val

[jameswangxin]

class CustomStack {
    private Deque<Integer> de = new LinkedList<>();
    AtomicInteger el = new AtomicInteger(0);
    private int sz = 0;
    public CustomStack(int maxSize) {
        sz = maxSize;
    }

    public void push(int x) {
        if (el.get() < sz) {
            de.offerLast(x);
            el.incrementAndGet();
        }
    }

    public int pop() {
        if (el.get() > 0) {
            el.decrementAndGet();
            return de.pollLast();
        } 
        return -1;
    }

    public void increment(int k, int val) {
        int pops = Math.min(k, el.get());
        Deque<Integer> temp = new LinkedList<>();
        for (int i = 0; i < pops; i++) {
            int newValue = de.pollFirst() + val;
            temp.offerLast(newValue);
        }

        while (temp.size() > 0) {
            int tmpVal = temp.pollLast();
            de.offerFirst(tmpVal);
        }
    }
}

/**
 * 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);
 */

[shuichicx]

class CustomStack:

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

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

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

    def increment(self, k: int, val: int) -> None:
        n=min(k,len(self.stack))
        for i in range(n):
            self.stack[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)

[JinhMa]

    List<Integer> stack;
    int size;
    public CustomStack(int maxSize) {
        this.stack = new ArrayList<Integer>(maxSize);
        this.size = maxSize;
    }

    public void push(int x) {
        if(stack.size()+1<=size){
            stack.add(x);
        }
    }

    public int pop() {
        if(stack.size() == 0){
            return -1;
        }
        int result = stack.get(stack.size()-1);
        stack.remove(stack.size()-1);
        return result;
    }

    public void increment(int k, int val) {
        for(int i=0;i<stack.size();i++){
            int var1 = stack.get(i);
            if(i<k){
                stack.set(i, var1+val);
            }
        }
    }
}

[Dtjk]

class CustomStack {
public:
    stack <int> stk;
    int sz;
    CustomStack(int maxSize) {
       sz = maxSize; 
    }

    void push(int x) {
        if ( stk.size() < sz ) stk.push(x);
    }

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

    void increment(int k, int val) {
        stack <int> stk_;
        while ( !stk.empty()  ) {stk_.push( stk.top() );stk.pop();}
        while ( !stk_.empty() && k > 0 ) {
            stk.push (stk_.top() + val);
            stk_.pop();
            k--;
        }
        while ( !stk_.empty() ) {
            stk.push(stk_.top());
            stk_.pop();
        }
    }
};