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

Categories:

题目描述
思路分析
1. 解法一：栈 + 延迟增量数组（推荐）
相似题目

题目描述

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

思路分析

解法一：栈 + 延迟增量数组（推荐）

核心思路：

用数组保存栈元素，用 inc[i] 记录对前 i 个元素的延迟增量。

increment(k, val) 只在 inc[k-1] 处累加，等出栈时再下放。

pop 时把 inc[top] 加到元素上，并将增量传递给 inc[top-1]。

复杂度分析：

时间复杂度：O(1) 每次操作。

空间复杂度：O(n)。

class CustomStack {
    private final int[] stack;
    private final int[] inc;
    private int size;

    public CustomStack(int maxSize) {
        stack = new int[maxSize];
        inc = new int[maxSize];
        size = 0;
    }

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

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

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

type CustomStack struct {
    stack []int
    inc   []int
    size  int
}

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

func (cs *CustomStack) Push(x int) {
    if cs.size == len(cs.stack) {
        return
    }
    cs.stack[cs.size] = x
    cs.size++
}

func (cs *CustomStack) Pop() int {
    if cs.size == 0 {
        return -1
    }
    i := cs.size - 1
    res := cs.stack[i] + cs.inc[i]
    if i > 0 {
        cs.inc[i-1] += cs.inc[i]
    }
    cs.inc[i] = 0
    cs.size--
    return res
}

func (cs *CustomStack) Increment(k int, val int) {
    i := k
    if i > cs.size {
        i = cs.size
    }
    i--
    if i >= 0 {
        cs.inc[i] += val
    }
}

相似题目

题目	难度	考察点
155. 最小栈	中等	栈
716. 最大栈	困难	栈
225. 用队列实现栈	简单	设计
232. 用栈实现队列	简单	设计
146. LRU 缓存	中等	设计

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/59237989