azl397985856 commented 2 years 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 次

yan0327 commented 2 years ago

思路：构造函数构造栈以及容量入栈需要判断栈是否满了，如果不满才可以进行入栈操作出栈需要判断栈是否为空，不为空才能出栈批量增加，要判断此时的k是否大于栈的元素，如果大于要置为k，此时一个for循环遍历批量增加

type CustomStack struct {
    stack []int
    total int
}

func Constructor(maxSize int) CustomStack {
    return CustomStack{[]int{},maxSize}
}

func (this *CustomStack) Push(x int)  {
    if len(this.stack) <this.total{
        this.stack = append(this.stack,x)
    }
}

func (this *CustomStack) Pop() int {
    if len(this.stack) == 0{
        return -1
    }
    out := this.stack[len(this.stack)-1]
    this.stack = this.stack[:len(this.stack)-1]
    return out
}

func (this *CustomStack) Increment(k int, val int)  {
    if k > len(this.stack){
        k = len(this.stack)
    }
    for i:=0;i<k;i++{
        this.stack[i] += val
    }
}

入栈，出栈时间复杂度O（N）增量操作O（k）空间复杂度O（N）

Alfie100 commented 2 years ago

【Python】直接模拟：

class CustomStack:

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

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

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

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

复杂度分析

时间复杂度：O(k)，其中 k 为增量函数 inc(int k, int val) 中的元素个数 k 。
空间复杂度：O(maxSize), 其中 maxSize 为栈中最多能容纳的元素数量。

zwx0641 commented 2 years ago

思路：使用数组来存放作为CusStack，cur表示当前需要填的数组位置
push就转化为放入cur位置，pop就为获取cur-1位置的值
inc就为数组前k个数加上val

class CustomStack {
    int[] stack;
    int cur = 0;
    public CustomStack(int maxSize) {
        stack = new int[maxSize];
    }

    public void push(int x) {
        if (cur >= stack.length) {
            return;
        }
        stack[cur] = x;
        cur++;
    }

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

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

时间：O(k) 空间：O(maxSize)

wxj783428795 commented 2 years ago

思路

js用数组模拟栈，可以直接用数组的push和pop方法表示栈的入栈和出栈

代码

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

/** 
 * @param {number} x
 * @return {void}
 */
CustomStack.prototype.push = function (x) {
    if (this.size < this.maxSize) {
        this.values.push(x);
        this.size += 1;
    }
};

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

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

复杂度分析

复杂度分析不是很会，不一定对，如果有错，请指正。

时间复杂度：
- push ：O(1)，数组在末位添加元素，复杂度为O(1)。
- pop：O(1)，数组从末尾删除元素，复杂度为O(1)。
- increment：O(min(k,N))，其中N为数组长度，k为需要操作的元素数量。
空间复杂度：O(N)，其中N为maxSize。

xianxianxianyu commented 2 years ago

链表或者数组都可以没啥好说的，两三分钟就完了

class CustomStack {
public:
    vector <int> v;
    int top, maxsize;

    CustomStack(int maxSize) {
        v.resize(maxSize);
        maxsize = maxSize;
        top = -1;
    }

    void push(int x) {
        if(top == maxsize - 1) return;
        v[++ top] = x;
    }

    int pop() {
        if(top == -1) return -1;
        top --;
        return v[top + 1];
    }

    void increment(int k, int val) {
        int lim = min(k, top + 1);
        for(int i = 0; i < lim; i ++) v[i] += val;
    }
};

BlessingLR commented 2 years ago

class CustomStack:
    def __init__(self, maxSize: int):
        self.maxSize = maxSize
        self.lst = []
        self.idx = 0

    def push(self, x: int) -> None:
        if self.idx < self.maxSize:
            self.idx += 1
            self.lst.append(x)

    def pop(self) -> int:
        if self.idx == 0:
            return -1
        self.idx -= 1
        return self.lst.pop()

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

yijing-wu commented 2 years ago

思路

using array to simulate stack

代码


class CustomStack {

    private int[] stack;
    private int pointer;
    private int maxSize;

    public CustomStack(int maxSize) {
        this.stack = new int[maxSize];
        this.pointer = 0;
        this.maxSize = maxSize;
    }

    public void push(int x) {
        if( pointer < maxSize ) {
            stack[pointer] = x;
            ++pointer;
        }
    }

    public int pop() {
        if( pointer > 0 ) {
            --pointer;
            return stack[pointer];
        } else {
            return -1;
        }
    }

    public void increment(int k, int val) {
        int min = Math.min(k, pointer);
        for(int i = 0; i < min; i++) {
            stack[i] += val;
        }
    }
}

复杂度分析

Time Complexitty
- SC = O(maxSize)
- CustomStack O(1)
- push TC = O(1)
- pop TC = O(1)
- increment TC = O(k)
Space Complexitty = O(maxSize)

falconruo commented 2 years ago

思路: 使用数组模拟栈

时间复杂度:

时间复杂度: O(1) - push, pop; O(k) - increment
空间复杂度: O(maxSize)

代码(C++):

class CustomStack {
public:
    CustomStack(int maxSize) {
        size = maxSize;
    }

    void push(int x) {
        if (st.size() >= size) return;
        st.push_back(x);
    }

    int pop() {
        if (st.size() == 0) return -1;
        int val = st.back();
        st.pop_back();
        return (val);
    }

    void increment(int k, int val) {
        int idx = (k <= st.size()) ? k : st.size();

        for (int i = 0; i < idx; ++i)
            st[i] += val;
    }
private:
    int size;
    vector<int> st;
};

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

ginnydyy commented 2 years ago

Problem

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

Note

Use int array and record the maxSize and curSize

Solution

class CustomStack {

    private int[] array;
    private int maxSize;
    private int curSize;

    public CustomStack(int maxSize) {
        this.array = new int[maxSize];
        this.maxSize = maxSize;
        this.curSize = 0;
    }

    public void push(int x) {
        if(this.curSize < this.maxSize){
            array[curSize++] = x;
        }
    }

    public int pop() {
        if(this.curSize > 0){
            return array[--curSize];
        }
        return -1;
    }

    public void increment(int k, int val) {
        if(curSize > 0){
            for(int i = 0; i < k && i < curSize; i++){
                array[i] += 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);
 */

Complexity

T: O(1) for push and pop, O(k) for increment.
S: O(n) n is the max size of the stack.

zhangzz2015 commented 2 years ago

思路

关键点如何处理incremental number。利用一个数组记录对应位置的incremental，当pop时，累加当前位置的incremental value，同时把该incremental value传递前一个index。使用如下例子 stack [ 1 2 3 4 5] incremental [100 100 100 100 100] 当pop 是 5 + 100 后stack [ 1 2 3 4] incremental [ 100 100 100 200] 再pop是 4 + 200 。这样起到累加的效果。时间复杂度为 O(1) ，空间复杂度为 O(N)，N为最大设置stack size。

关键点

代码

语言支持：C++

C++ Code:


class CustomStack {
public:

    vector<int> stack; 
    int iSize; 
    vector<int> incSum; 
    CustomStack(int maxSize) {

        iSize = maxSize; 
        incSum.assign(iSize, 0); 
    }

    void push(int x) {

        if(stack.size() < iSize)
        {
            stack.push_back(x); 
        }        
    }

    int pop() {

        if(stack.size())
        {
            int index = stack.size()-1;
            int addValue = incSum[index];
            if(index>0)
            {
                incSum[index-1] += addValue;                  
            }
            incSum[index] =0;            
            int ret = stack.back() + addValue; 
            stack.pop_back();
            return ret; 
        }
        else
            return -1; 

    }

    void increment(int k, int val) {

        int index = min(k, int(stack.size()) ); 
        if(index>0)
        {
            incSum[index-1] += val; 
        }        
    }
};

yangziqi1998666 commented 2 years ago

class CustomStack {
    private int maxSize;
    private int[] stack;
    private int pointer;

    public CustomStack(int maxSize) {
        this.maxSize = maxSize;
        this.pointer = -1;
        stack = new int[maxSize];
    }

    public void push(int x) {
        if (pointer != maxSize-1){
            pointer++;
            stack[pointer] = x;
        }

    }

    public int pop() {
        if (pointer == -1)
            return -1;
        pointer--;
        return stack[pointer+1];

    }

    public void increment(int k, int val) {
        for(int i = 0; i <= pointer && i < k; i++){
            stack[i] += 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);
 */

zwmanman commented 2 years ago

思路

Create a stack and a global variable to keep the max size

代码

class CustomStack(object):

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

    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        if len(self.stack) < self.maxEle:
            self.stack.append(x)

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

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

复杂度分析

时间复杂度：O(min(len(stack), k))，为增量k和数组长度中的较小值
空间复杂度：O(Maxsize)

ZhangNN2018 commented 2 years ago

思路

创建列表[]，对列表操作实现相关功能。

代码

class CustomStack(object):

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

    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        if len(self.stack)<self.maxSize:
            self.stack.append(x)

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

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

复杂度

时间复杂度: O(N), 由increment的遍历带来的；
空间复杂度：O(N), 栈的生成占用的空间。

CoreJa commented 2 years ago

思路

naive思路非常好想，按照需求实现即可

但是考虑到increment操作针对的是栈，栈在这里只会访问栈顶，所以可以考虑对increment使用lazy操作只在出栈的时候去进行之前的increment操作，以规避对栈内元素过多的操作

具体就是每次increment并不直接增加到它要求的栈底的k个元素，而是用另一个数组lazy_inc保存起来，只在pop的时候去加上lazy_inc的top-1元素，并将这个increment加到数组中的前一个元素中(这样就把它继承下去了)

代码

# naive思路
class CustomStack1:

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

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

    def pop(self) -> int:
        if self.cur <= 0:
            return -1
        self.cur -= 1
        return self.stack[self.cur]

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

#  lazy_increment做法
class CustomStack:
    def __init__(self, maxSize: int):
        self.top = 0
        self.stack = [0] * maxSize
        self.add = [0] * maxSize

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

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

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

复杂度

TC: push O(1), increment O(1), pop O(1) SC: O(n)

CodeWithIris commented 2 years ago

Note

Use vector to store the data. Record the curIndex and execute the push, pop and increment operation through the curIndex.

Solution


class CustomStack {
public:
    vector<int> stk;
    int top, size;
    CustomStack(int maxSize) {
        stk.resize(maxSize);
        size = maxSize;
        top = -1;
    }

    void push(int x) {
        if(top != size -1){
            ++top;
            stk[top] = x;
        }
    }

    int pop() {
        if(top == -1) return -1;
        --top;
        return stk[top + 1];
    }

    void increment(int k, int val) {
        for(int i = 0; i < min(top + 1, k); ++i){
            stk[i] += val;
        }
    }
};

Complexity

T: O(1) for push and pop operation, O(k) for increment operation
S: O(n): n is the 'maxSize'

Husky-Gong commented 2 years ago

思路

使用ArrayList模拟实现
构造函数：初始化ArrayList和maxSize
push：如果list.size()<maxSize，才向其中添加数字；否则，返回。
pop：判断list中是否有函数，有的话返回，并remove掉当前数字。否则，返回-1
increment：【bottom】代表从list的0开始计算的k个元素进行加val

代码

class CustomStack {
    List<Integer> list;
    int maxSize;

    public CustomStack(int maxSize) {
        list = new ArrayList<>();
        this.maxSize = maxSize;
    }

    public void push(int x) {
        if (maxSize > list.size()) {
            list.add(x);
        } else {
            return;
        }
    }

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

    public void increment(int k, int val) {
        // bottom is start from 0
        int cur = 0;

        while (cur <= list.size() - 1 && k > 0) {
            int newVal = list.get(cur) + val;
            list.set(cur, newVal);
            cur++;
            k--;
        }
    }
}

复杂度

时间复杂度：O(n) 因为有increment操作，可能需要遍历所有数空间复杂度：O(n) 构造了新的数据结构用于存放数字

rzhao010 commented 2 years ago

Thoughts

Using two stack to stimulate the customStack, so for PUSH and POP, we can just go with the same operations. The second Stack will be used to hold the POP of first Stack, then we use an var to count and compare with k.

Code

    Stack<Integer> stack;
    Stack<Integer> stack2 = new Stack<Integer>();
    int s;

    public CustomStack(int maxSize) {
        stack = new Stack<Integer>();
        s = maxSize;
    }

    public void push(int x) {
        if (stack.size() < s) {
            stack.push(x);
        } else {
            return;
        }
    }

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

    public void increment(int k, int val) {
        int count = 0;
        if (k > stack.size()) {
            while (stack.size() > 0) {
                int tmp = stack.pop();
                stack2.push(tmp + val);
            }
            while (stack2.size() > 0) {
                int tmp = stack2.pop();
                stack.push(tmp);
            }
        } else {
            while (stack.size() > 0) {
                int tmp = stack.pop();
                stack2.push(tmp);
            }
            while (stack2.size() > 0) {
                int tmp = stack2.pop();
                count++;
                if (count <= k) {
                    stack.push(tmp + val);
                } else {
                    stack.push(tmp);
                }
            }
        }
    }

Time Complexity

Time: PUSH and POP O(1), increment O(k)
Space: O(n), n is the size of the stack

moirobinzhang commented 2 years ago

Idea: Use List to simulate Stack

Code:

public class CustomStack {

public List<int> cList {get; set;}
public int maxCount {get; set;}

public CustomStack(int maxSize) {
    cList = new List<int>();
    maxCount = maxSize;        
}

public void Push(int x) {
    if (cList.Count >= maxCount)
        return;

    cList.Add(x);
}

public int Pop() {
    if (cList == null || cList.Count == 0)
        return -1;

    int popValue = cList[cList.Count - 1];
    cList.RemoveAt(cList.Count - 1);
    return popValue;
}

public void Increment(int k, int val) {
    if (cList == null || cList.Count == 0)
        return;

    int len = cList.Count >= k ? k : cList.Count;

    for (int i = 0; i < len ; i++)
        cList[i] += val;
}

}

Complexity T: Push: O(1), Pop: O(1), Increment: O(N) S: O(n)

Frederickfan commented 2 years ago

Idea:

Use the python list to simulate stack. The only feature we need to add is to increase last k elements by val.

Code:

class CustomStack:

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

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

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

    def increment(self, k: int, val: int) -> None:
        length = min(k, len(self.array))

        for i in range(length):
            self.array[i] += val

Complexity

Time: Push: O(1) Pop: O(1) Increment: O(min(k, n)) Space: O(n)

wangzehan123 commented 2 years ago

代码

语言支持：Java

Java Code:


class CustomStack {

    int[] data;
    int head;

    public CustomStack(int maxSize) {

        data = new int[maxSize];
        head = -1;
    }

    public void push(int x) {

        if (head == data.length - 1)
            return;

        data[++head] = x;
    }

    public int pop() {

        if (head == -1)
            return -1;

        return data[head--];
    }

    public void increment(int k, int val) {

        for (int i = 0; i < Math.min(k, head + 1); i++)
            data[i] += 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);
 */

SHAO-Nuoya commented 2 years ago

类的用法

Code

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:
            ans = self.stack[-1]
            del self.stack[-1]
            return ans
        return -1

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

Yrtryannn commented 2 years ago

class CustomStack {

    int[] data;
    int head;

    public CustomStack(int maxSize) {

        data = new int[maxSize];
        head = -1;
    }

    public void push(int x) {

        if (head == data.length - 1)
            return;

        data[++head] = x;
    }

    public int pop() {

        if (head == -1)
            return -1;

        return data[head--];
    }

    public void increment(int k, int val) {

        for (int i = 0; i < Math.min(k, head + 1); i++)
            data[i] += val;
    }
}

FayePei commented 2 years ago

class CustomStack { int top; public CustomStack(int maxSize){ int[] stack=new int[maxSize]; top=-1; }

 public void Push(int x) { //no need to return, for the void method
     if(top!=stack.length-1){
         top++;
         stack[top]=x;
     }
 }
 public int Pop() {
    if(top=-1){
        return -1;
    }--top;
     return stack[top+1];

 }
 public void Increment(int k, int val) {
     int limit=Math.min(k,top+1);
    for(int i=0;i<limit;i++){
        stack[i]=stack[i]+val;
    } 

 }

}

cszys888 commented 2 years ago

思路

用O(1)的时间复杂度实现所有的操作，除了increment function

代码

class CustomStack:

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

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

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

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

复杂度

时间复杂度: CustomStack: O(1) push: O(1) pop: O(1) increment: O(N) 空间复杂度： O(N)

declan92 commented 2 years ago

思路

使用数组实现,第一位的值保存栈顶位置指针,数组尾部为栈顶;
初始化:数组长度maxSize+1,ans[0] = 0,size = maxSize;
push(val):数组尾部增加值,栈顶指针++;

pop():数组尾部弹出值,栈顶指针--; java

class CustomStack {
private int[] ans;
private size;

public CustomStack(int maxSize) {
    ans = new int[maxSize+1];
    size = maxSize;
    ans[0] = 0;
}

public void push(int x) {
    if(ans[0] < size){
        ans[++ans[0]] = x;
    }
}

public int pop() {
    if(ans[0] > 0){
        int res = ans[ans[0]];
        ans[ans[0]--] = 0;
        return res;
    }
    return -1;
}

public void increment(int k, int val) {
    int min = Math.min(ans[0],k);
    for(int i = 1;i <= min; i++){
        ans[i] = ans[i] + val;
    }
}
}

复杂度:
时间:Custom(int maxSize): O(1); push(int x):O(1); pop():O(1); increment(int k, int val):O(n),n为栈深;
额外空间:O(1)

ZacheryCao commented 2 years ago

Idea

Array

Code

class CustomStack:

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

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

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

    def increment(self, k: int, val: int) -> None:
        if len(self.cache) <= k:
            for i in range(len(self.cache)):
                self.cache[i] += val
        else:
            for i in range(k):
                self.cache[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:

Tine: Push: O(1). Pop: O(1). Increment: O(min(K, N)) Space: O(N)

Alexno1no2 commented 2 years ago

题解使用数组模拟栈，用一个变量 top 来记录当前栈顶的位置。对于 push 操作，首先判断当前元素的个数是否达到上限，如果没有达到，就把 top 后移一个位置并添加一个元素。对于 pop 操作，首先判断当前栈是否为空，非空返回栈顶元素并将 top 前移一位，否则返回 -1。对于 inc 操作，直接对栈底的最多 k 个元素加上 val。代码 class CustomStack:

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

def push(self, x: int) -> None:
    if self.top != len(self.stk) - 1:
        self.top += 1
        self.stk[self.top] = x

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

def increment(self, k: int, val: int) -> None:
    lim = min(k, self.top + 1)
    for i in range(lim):
        self.stk[i] += val

分析时间复杂度：初始化（构造函数）、push 操作和 pop 操作的渐进时间复杂度为 O(1)，inc 操作的渐进时间复杂度为 O(k)。空间复杂度：这里用到了一个长度为 maxSize 的数组作为辅助空间，渐进空间复杂度为 O(maxSize)。

Yutong-Dai commented 2 years ago

代码

class CustomStack:

    def __init__(self, maxSize: int):
        self.maxSize = maxSize
        self.size = 0
        self.lst = [None] * maxSize

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

    def pop(self) -> int:
        if self.size == 0:
            return -1
        else:
            item = self.lst[self.size-1]
            self.size -= 1
            return item

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

复杂度:

时间

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

空间复杂度：

push: O(2)
pop: (1)
increment: O(1)

1052561252 commented 2 years ago

解题思路

解题思路： 1.直观上的解题方式是用数组来实现，用int变量curSize记录当前stack中元素的数量，因此curSize的初始化值为0 2.每次调用push()时，先检查curSize是否等于maxSize。如果不是，使得stack[curSize]=x，然后curSize++ 3.每次调用pop()时，先检查curSize是否等于0。如果是，直接返回-1；如果不是，先让curSize--，然后num=stack[curSize]。最后返回num 4.每次调用increment()时，取得curSize和k中的较小值为k，遍历stack[0]-stack[k-1]，使得stack[i]+=val

代码

class CustomStack {

    private int[] stack;
    private int maxSize;
    private int curSize;

    public CustomStack(int maxSize) {
        this.stack = new int[maxSize];
        this.maxSize = maxSize;
        this.curSize = 0;
    }

    public void push(int x) {
        if (curSize < maxSize) {
            stack[curSize] = x;
            curSize++;
        }
    }

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

        int num = stack[curSize];
        curSize--;
        return num;
    }

    public void increment(int k, int val) {
        k = Math.min(k, curSize);
        for (int i = 0; i < k; i++) {
            stack[i] += val;
        }
    }
}

复杂度分析

时间复杂度：

push()：O(1)
pop()：O(1)
increment()：O(k)

kandejiandefeng commented 2 years ago

/**
 * @param {number} maxSize
 */
var CustomStack = function(maxSize) {
    this.value = new Array();
    this.size = maxSize;
};

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

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

/** 
 * @param {number} k 
 * @param {number} val
 * @return {void}
 */
CustomStack.prototype.increment = function(k, val) {
    let i = 0;
    for(i; i < k; i++) {
        if(!this.value[i]) {
            break;
        }
        this.value[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)
 */

Toms-BigData commented 2 years ago

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

思路

数组模拟栈，唯一区别在inc,比较数组长度和K值，再循环增加

Golang代码

type CustomStack struct {
    Stack []int

}

func Constructor(maxSize int) CustomStack {
    if maxSize < 0{
        return CustomStack{}
    }
    return CustomStack{
        Stack: make([]int , 0, maxSize),
    }
}

func (this *CustomStack) Push(x int)  {
    if len(this.Stack) < cap(this.Stack){
        this.Stack = append(this.Stack, x)
    }
}

func (this *CustomStack) Pop() int {
    if len(this.Stack) == 0 {
        return -1
    }else {
        pop := this.Stack[len(this.Stack)-1]
        this.Stack = this.Stack[:len(this.Stack)-1]
        return pop
    }
}

func (this *CustomStack) Increment(k int, val int)  {
    change_num := int(math.Min(float64(k), float64(len(this.Stack))))
    for i :=0;i<change_num;i++{
        this.Stack[i] += val
    }
}

hdyhdy commented 2 years ago

思路：结构体添加一个变量c，用于记录需要操作的位置。push和pop需要注意的地方在注意变量c在不同值的情况下操作是不一样的。

type CustomStack struct {
    stack []int
    c int
}

func Constructor(maxSize int) CustomStack {
    return CustomStack{
        stack : make([]int,maxSize),
        c : 0,
    }
}

func (this *CustomStack) Push(x int)  {
    if this.c < len(this.stack){
        this.stack[this.c] = x
        this.c ++ 
    }
}

func (this *CustomStack) Pop() int {
    if this.c != 0 {
        this.c--
        return this.stack[this.c]
    }
    return -1
}

func (this *CustomStack) Increment(k int, val int)  {
    if k > this.c {
        for i := 0; i < this.c; i++ {
            this.stack[i] += val
        }
    } else {
        for i := 0; i < k; i++ {
            this.stack[i] += val
        }
    }

}

/**
 * Your CustomStack object will be instantiated and called as such:
 * obj := Constructor(maxSize);
 * obj.Push(x);
 * param_2 := obj.Pop();
 * obj.Increment(k,val);
 */

复杂度：时间：初始化、Pop和Push都为1，inc循环，所以最多为k 空间：创建了maxsize大小的，所以空间为maxsize

luo-FrontEnd commented 2 years ago

JavaScript 思路: 1、利用JS的push、pop方法,原理很简单,但是时间复杂度高,因为如果初始化没有给数组每项赋值,然后每次push都会是O(n)的时间,因为每次都需要重新申请地址. 2、修改JS的push、pop方法,每次操作记录当前下标,这样能将push方法、pop方法降低O(1)的时间复杂度

/**
 * @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 {number}
 */
CustomStack.prototype.pop = function() {
    return this.stack.length > 0 ? this.stack.pop() : -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)
 */

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

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

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

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

提交时证明我对于思路1的push、pop的时间复杂度是错误的,可能由于V8的优化,思路1比思路2快. 时间复杂度: push:O(1) pop:O(1) increment:O(min(n, k)), n为数组长度

aladingzl commented 2 years ago

思路

用数组模拟一个栈，根据条件进行出栈跟入栈的操作，判断 k 与 length 的大小，对相应数量的元素进行增加 val 的操作

代码

/**
 * @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) {
        this.stack.push(x);
    }
};

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

};

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

复杂度分析

时间复杂度：pop 和 push 操作时间复杂度为 O(1) 增量操作的时间复杂度为 O(k)
空间复杂度：O(maxSize)

Joyce94 commented 2 years ago

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:
            top = self.stack[-1]
            self.stack.pop()
            return top 
        else:
            return -1 

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

CodingProgrammer commented 2 years ago

思路

用数组模拟栈，从数组尾部添加、弹出，increase的时候，从第0个元素到第 min(k, arr.size) 元素增加 val

代码

class CustomStack {
    int capacity;
    int count;
    List<Integer> myStack;

    public CustomStack(int maxSize) {
        this.capacity = maxSize;
        this.count = 0;
        this.myStack = new LinkedList<>();

    }

    public void push(int x) {
        if (this.count < this.capacity) {
            this.count++;
            this.myStack.add(x);
        }
    }

    public int pop() {
        if (this.count == 0) {
            return -1;
        }
        // 弹出栈顶元素
        int remove = this.myStack.remove(--this.count);
        return remove;
    }

    public void increment(int k, int val) {
        if (k > this.count) {
            k = this.count;
        }
        for (int i = 0; i < k; i++) {
            this.myStack.set(i, this.myStack.get(i) + val);
        }
    }
}

复杂度

Time: O(N)
Space: O(N)

biaohuazhou commented 2 years ago

思路

使用数组实现栈

代码

    class CustomStack {
        private int[] stack;
        private int maxSize;
        private int curSize;

        public CustomStack(int maxSize) {
            stack = new int[maxSize];
            this.maxSize = maxSize;
            curSize = 0;
        }

        public void push(int x) {
            if (curSize < maxSize) {
                stack[curSize++] = x;
            }
        }

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

        public void increment(int k, int val) {
            k = Math.min(k, curSize);
            for (int i = 0; i < k; i++) {
                stack[i] = stack[i]+val;

            }

        }
    }

复杂度分析 时间复杂度： push：O(1) pop:O(1) increment:O(k) 空间复杂度：$O(k)$

gova-i267 commented 2 years ago

思路：用数组实现

nowIndex 代表当前元素的位置，-1 为栈空
maxSize 为栈最大，nowIndex == maxSize - 1 时，栈满
每 push 一次，nowIndex 往后移动一位
每 pop 一次，nowIndex 往前移动一位
increment 时，遍历 i 从 0 开始，需要满足 i < k && i <= nowIndex

java

class CustomStack {
    int maxSize = 0;
    int nowIndex = -1;
    int[] arr;
    public CustomStack(int maxSize) {
        this.maxSize = maxSize;
        arr = new int[maxSize];
    }

    public void push(int x) {
        if (nowIndex == maxSize-1) {
            return;
        }
        arr[++nowIndex] = x;
    }

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

    public void increment(int k, int val) {
        for (int i=0;i<k && i<=nowIndex;i++) {
            arr[i] += 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);
 */

复杂度分析

时间复杂度
- push O(1)
- pop O(1)
- increment:O(k)最大O(n)
空间复杂度
- O(maxSize)

Myleswork commented 2 years ago

思路

用数组模拟栈

栈有两种，一种是top指向栈顶元素，另一种是top指向栈顶元素上一空间。我模拟的是第一种。

代码

class CustomStack {
public:
    //用数组模拟栈，便于实现inc
    //移动top指针从而实现
    vector<int> Stack;  //栈
    int top;            //栈顶指针

    CustomStack(int maxSize) {
        Stack.resize(maxSize);
        top = -1;
    }

    void push(int x) {
        if(top!=Stack.size()-1){
            ++top;
            Stack[top] = x;
        }
    }

    int pop() {
        if(top == -1) return -1;
        --top;
        return Stack[top+1];
    }

    void increment(int k, int val) {
        for(int i = 0;i<k && i<Stack.size();i++){
            Stack[i] += 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);
 */

复杂度分析

push：O(1)

pop：O(1)

increment：O(n)

有个问题

void push(int x) {
        if(top!=Stack.size()-1){
            ++top;
            Stack[top] = x;
        }
    }
//if里面的语句用!=就是对的
//if里面的语句用<就错了
//我不理解

yunomin commented 2 years ago

python

class CustomStack:

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

    def push(self, x: int) -> None:
        if self.space_left > 0:
            self.l.append(x)
            self.space_left -= 1

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

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

xingzhan0312 commented 2 years ago

Note

Push O(1), Pop O(1), Increment O(n), n is min(this.size,k);
Space Complexity: O(n)

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

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

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

/** 
 * @param {number} k 
 * @param {number} val
 * @return {void}
 */
CustomStack.prototype.increment = function(k, val) {
    for(let i=Math.min(k-1,this.size-1);i>=0;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)
 */

linyang4 commented 2 years ago

思路

构造函数: 创建数组保存栈的值, 并且创建一个变量用于记录数组最大容纳数量
push操作: 先比较数组的长度和最大容纳数量, 如果2个值相等, 不进行任何操作, 否则把数据添加到数组末尾
pop操作: 先判断数组是否为空, 为空就返回-1, 否则移除数组最后一位的数据并返回
inc操作: 取数组的长度和k中较小的进行遍历, 然后进行加等操作

代码

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

CustomStack.prototype.push = function(x) {
    if (this._data.length !== this._maxSize) {
        this._data.push(x)
    }
};

CustomStack.prototype.pop = function() {
    if (this._data.length !== 0) {
        return this._data.pop()
    } else {
        return -1
    }
};

CustomStack.prototype.increment = function(k, val) {
    for(let i = 0; i < Math.min(k, this._data.length); i++) {
        this._data[i] = this._data[i] + val
    }
};

复杂度

时间复杂度

push: O(1)
pop: O(1)
inc: O(min(K, N)),

LuoXingbiao commented 2 years ago

思路

用一个数组模拟栈，top指针指向当前栈顶。

代码

class CustomStack {

    int[] data;
    int top;
    public CustomStack(int maxSize) {
        data = new int[maxSize];
        top = -1;
    }

    public void push(int x) {
        if(top < data.length - 1){
            data[++top] = x;
        }
    }

    public int pop() {
        int peek = -1;
        if(top >= 0){
            peek = data[top--];
        }
        return peek;
    }

    public void increment(int k, int val) {
        for(int i = 0; i < Math.min(k, top + 1);i++){
            data[i] += 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);
 */

复杂度

时间复杂度：push(),pop()在O(1)时间内完成，increment在O(n)的时间内完成。故时间复杂度为O(n)。空间复杂度：O(n)

tangjy149 commented 2 years ago

思路

用数组进行模拟即可，c++的vector本身就有push_back和pop_back的使用方式，但该题需注意，需要对添加的数进行计数，因为本身数组的大小已经被限制了maxsize，因此不能通过数组的size进行判断数据（应该），所以我添加了count进行计算当前数组已经有多少数据，来对pop和push情况进行判断

代码

class CustomStack {
public:
    int count;// 计数
    vector<int> helper;
    CustomStack(int maxSize) {
        helper.resize(maxSize);
        count=0;
    }

    void push(int x) {
        if(count<helper.size()){
            helper[count]=x;
            count++;
        }
    }

    int pop() {
        if(--count<0){
            count=0;
            return -1;
        }
        return helper[count];
    }

    void increment(int k, int val) {
        for(int i=0;i<min(k,count);i++){
            helper[i]+=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);
 */

复杂度

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

herbertpan commented 2 years ago

思路

没什么特别的，标准的用array 模拟stack

top指针表示栈顶
bottom 指针表示栈底
size 表示当前栈大小：push pop 操作相关
array[maxSize + 1]做内部数据结构：为什么+1，模拟stack full时top指针的位置

代码

class CustomStack {
    private int maxSize;
    private int size;
    private int top;
    private int bot;

    private int[] stack;

    public CustomStack(int maxSize) {
        this.size = 0;
        this.top = 0;
        this.bot = 0;

        this.maxSize = maxSize;
        this.stack = new int[maxSize+1];
    }

    public void push(int x) {
        if (this.size == this.maxSize) {
            // do nothing
        } else {
            this.stack[this.top++] = x;
            this.size++;
        }
    }

    public int pop() {
        if (this.size == 0) {
            return -1;
        } else {
            this.top--;            
            this.size--;
            return this.stack[this.top];
        }
    }

    public void increment(int k, int val) {
        if (k > this.maxSize) {
            k = this.maxSize;
        }

        for (int i = this.bot; i < k && i < this.top; i++) {
            this.stack[i] += val;
        }
    }
}

复杂度分析

时间复杂度：push,pop都是O(1), increment是O(min(K, maxSize))
空间复杂度：O(maxSize)

Bochengwan commented 2 years ago

思路

利用一个额外的stack来存delta

代码

class CustomStack:

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

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

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

        if self.delta:
            self.delta[-1]+=delta
        return self.myStack.pop()+delta

    def increment(self, k: int, val: int) -> None:
        length = len(self.myStack)
        if length ==0:
            return None
        inc_length = k
        if k>length:
            inc_length = length     
        self.delta[inc_length-1]+=val

复杂度分析

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

zjsuper commented 2 years ago

class CustomStack:

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

    def push(self, x: int) -> None:
        if len(self.s)==self.ms:
            pass
        else:
            self.s.append(x)

    def pop(self) -> int:
        if not self.s:
            return -1
        temp = self.s.pop()
        return temp

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

spacker-343 commented 2 years ago

思路

由于栈容量大小固定，因此考虑使用数组来模拟，并用一个index指针指向栈顶元素

代码

class CustomStack {

    int[] customStack;
    int index;

    public CustomStack(int maxSize) {
        customStack=new int[maxSize];
        index=-1;
    }

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

    public int pop() {
        if(index==-1){
            return -1;
        }
        int res=customStack[index];
        customStack[index--]=0;
        return res;
    }

    public void increment(int k, int val) {
        int inc=Math.min(index+1, k);
        for(int i=0; i<inc; i++){
            customStack[i]+=val;
        }
    }
}

复杂度

时间复杂度: O(1) push pop O(min(index+1, k)) increment 空间复杂度：O(1)

shamworld commented 2 years ago

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

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

/**
 * @return {number}
 */
CustomStack.prototype.pop = function() {

    if(this.stackList.length==0) return -1;
    return this.stackList.pop();
};

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

GaoMinghao commented 2 years ago

思路

栈具有先进后出的特性，可以用数组来实现

代码

class CustomStack {
    int[] stack;
    int maxSize = 0;
    int size = 0;

    public CustomStack(int maxSize) {
        this.stack = new int[maxSize];
        this.maxSize = maxSize;
    }

    public void push(int x) {
        if(size<maxSize) {
            this.stack[size] = x;
            size++;
        }
    }

    public int pop() {
        if(size>0) {
            int result = stack[size -1];
            size --;
            return result;
        }
        return -1;
    }

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

时空复杂度

时间复杂度 push O(1) pop O(1) increment O(min(K,N)) 空间复杂度 O(1)

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

【Day 3 】2021-12-14 - 1381. 设计一个支持增量操作的栈 #4

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

入选理由

题目地址

前置知识

题目描述

思路

代码

复杂度分析

思路

代码

Problem

Note

Solution

Complexity

思路

关键点

代码

思路

代码

思路

代码

复杂度

思路

代码

复杂度

Note

Solution

思路

代码

复杂度

Idea:

Code:

Complexity

代码

类的用法

Code

思路

代码

复杂度

Idea

Code

Complexity:

代码

复杂度:

解题思路

代码

复杂度分析

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

思路

Golang代码

思路

代码

思路

代码

复杂度

思路

代码

思路：用数组实现

java

复杂度分析

思路

代码

有个问题

python

Note

思路

代码

复杂度

时间复杂度

思路

代码

复杂度

思路

代码

思路

代码

思路

代码