azl397985856 commented 2 months ago

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 次

akxuan commented 2 months ago

很简单的题，提交之前要检查一下，比如这个题的K 是从bottom 开始算的

class CustomStack:

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

    def push(self, x: int) -> None:
        if len(self.stack) == self.size: 
            return None
        else: 
            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(k): 
            if i == len(self.stack):
                break
            self.stack[i] += val

Fightforcoding commented 2 months ago

class CustomStack:

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

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

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

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

time complexity O(1) space complexity O(n)

godkun commented 2 months ago

思路

数据结构：栈
算法：pop 、push 、迭代、循环

代码

TypeScript实现

class CustomStack {
  private maxSize: number;
  private stack: number[];
  constructor(maxSize: number) {
    this.maxSize = maxSize;
    this.stack = [];
  }

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

  pop(): number {
    if (this.stack.length == 0) return -1;
    else {
      const popResult = this.stack.pop() as number;
      return popResult;
    }
  }

  increment(k: number, val: number): void {
    const len = this.stack.length
    for (let index = 0; index < k && index < len; index++) {
      this.stack[index] = this.stack[index] + val
    }
  }
}

复杂度分析

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

CelesteXiong commented 2 months ago

Solution 1

Intuition

Algorithm

class CustomStack:

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

    def push(self, x: int) -> None:
        if self.currentSize < self.maxSize:
            self.stack.append(x)
            self.currentSize += 1
        else: return

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

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

Complexity analysis

Time: push O(1), Pop O(1), Increment O(min(k, n)), n is maxSize Space: O(1)

Solution 2

Intuition

Optimize the increment by storing the incremented value and add to the top value when top value is popped. It's like a lazy update. After the top value is generated, accumulatively add the current incremented value to previous incremented value, and clear the current incremented value since it's already been added to the popped top value.

Algorithm

class CustomStack:

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

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

    def pop(self) -> int:
        if self.topIndex >= 0: 
            top = self.stack[self.topIndex] + self.delta[self.topIndex]

            # accumulate delta
            if self.topIndex >= 1:
                self.delta[self.topIndex-1] += self.delta[self.topIndex]
            self.delta[self.topIndex] = 0

            self.topIndex -= 1
            return top
        else: return -1

    def increment(self, k: int, val: int) -> None:
        boundary = min(k-1, self.topIndex)
        if boundary >= 0:
            self.delta[boundary] += 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)

Complexity analysis

Time: push O(1), Pop O(1), Increment O(1) Space: O(n)

zjy-debug commented 2 months ago

思路

初始化：创建一个最大容量为maxSize的栈，初始时为空。

推入元素 (push)：只要栈未满，就可以向栈中添加新元素。

弹出元素 (pop)：从栈顶移除元素。如果栈为空时尝试弹出，返回-1。如果栈中有元素，返回栈顶元素的值，并将该值从栈中移除。

增量操作 (increment)：使栈底的前k个元素的值增加val。如果栈中元素不足k个，则所有元素的值都增加val。

代码

class CustomStack:

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

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

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

        if len(self.inc) > 1:
            self.inc[-2] += self.inc[-1]

        return self.inc.pop() + self.stack.pop()

    def increment(self, k: int, val: int) -> None:
        if k > len(self.stack):
            k = len(self.stack)
        if k > 0:
            self.inc[k - 1] += val

复杂度

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

DADAHUI commented 2 months ago

typedef struct {
    int maxSize;
    int curSize;
    int* customStack;
} CustomStack;

CustomStack* customStackCreate(int maxSize) {
    CustomStack* myCustomStack = (CustomStack*)malloc(sizeof(CustomStack));
    myCustomStack->maxSize = maxSize;
    myCustomStack->curSize = 0;
    myCustomStack->customStack = (int*)malloc(sizeof(int) * maxSize);
    return myCustomStack;
}

void customStackPush(CustomStack* obj, int x) {
    // 判空
    if (obj == NULL || obj->customStack == NULL)
        return;
    if (obj->curSize >= obj->maxSize) 
        return;
    obj->customStack[obj->curSize] = x;
    obj->curSize++;
}

int customStackPop(CustomStack* obj) {
    // 判空
    if (obj == NULL || obj->customStack == NULL)
        return -1;
    int ret = 0;
    // --curSize
    if (obj->curSize) {
        ret = obj->customStack[--obj->curSize];
    } else {
        ret = -1;
    }
    return ret;
}

void customStackIncrement(CustomStack* obj, int k, int val) {
    // 判空
    if (obj == NULL || obj->customStack == NULL)
        return;
    if (k > obj->maxSize) {
        for (int i = 0; i < obj->maxSize; ++i) {
            obj->customStack[i] += val;
        }
    } else {
        for (int i = 0; i < k; ++i) {
            obj->customStack[i] += val;
        }
    }
}

void customStackFree(CustomStack* obj) {
    if (obj == NULL || obj->customStack == NULL)
        return;
    free(obj->customStack);
    obj->customStack = NULL;
    free(obj);
    obj = NULL;
}

edwineo commented 2 months ago

代码

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

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

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

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

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

leetcode-pp / 91alg-14-daily-check

【Day 3 】2024-08-17 - 1381. 设计一个支持增量操作的栈 #9

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

入选理由

题目地址

前置知识

题目描述

思路

代码

TypeScript实现

Solution 1

Intuition

Algorithm

Complexity analysis

Solution 2

Intuition

Algorithm

Complexity analysis

思路

代码

复杂度

代码