LeetCode 面试题 03.03. 堆盘子

Categories:

题目描述
思路分析
1. 解法一：链表数组模拟（推荐）
相似题目

题目描述

✅ 面试题 03.03. 堆盘子

思路分析

解法一：链表数组模拟（推荐）

核心思路：

使用一个 List<Deque<Integer>> 维护多个子栈，每个子栈容量上限为 cap

push：若末尾子栈未满则直接压入，否则新建子栈；若 cap <= 0 则不操作

pop：弹出末尾子栈栈顶；若末尾子栈为空则移除该子栈

popAt(index)：弹出指定子栈栈顶；若该子栈为空则移除（不做后续整理，直接移除空栈）

复杂度分析：

时间复杂度：push/pop O(1)，popAt O(1)

空间复杂度：O(n)，其中 n 为元素总数

class StackOfPlates {

    private List<Deque<Integer>> stacks;
    private int cap;

    public StackOfPlates(int cap) {
        this.cap = cap;
        this.stacks = new ArrayList<>();
    }

    public void push(int val) {
        if (cap <= 0) {
            return;
        }
        // 末尾子栈已满或不存在时新建子栈
        if (stacks.isEmpty() || stacks.get(stacks.size() - 1).size() == cap) {
            stacks.add(new ArrayDeque<>());
        }
        stacks.get(stacks.size() - 1).push(val);
    }

    public int pop() {
        return popAt(stacks.size() - 1);
    }

    public int popAt(int index) {
        if (index < 0 || index >= stacks.size()) {
            return -1;
        }
        Deque<Integer> stack = stacks.get(index);
        if (stack.isEmpty()) {
            return -1;
        }
        int val = stack.pop();
        // 子栈弹空后移除
        if (stack.isEmpty()) {
            stacks.remove(index);
        }
        return val;
    }
}

type StackOfPlates struct {
    stacks [][]int
    cap    int
}

func Constructor(cap int) StackOfPlates {
    return StackOfPlates{cap: cap}
}

func (s *StackOfPlates) Push(val int) {
    if s.cap <= 0 {
        return
    }
    // 末尾子栈已满或不存在时新建子栈
    if len(s.stacks) == 0 || len(s.stacks[len(s.stacks)-1]) == s.cap {
        s.stacks = append(s.stacks, []int{})
    }
    last := len(s.stacks) - 1
    s.stacks[last] = append(s.stacks[last], val)
}

func (s *StackOfPlates) Pop() int {
    return s.PopAt(len(s.stacks) - 1)
}

func (s *StackOfPlates) PopAt(index int) int {
    if index < 0 || index >= len(s.stacks) {
        return -1
    }
    stack := s.stacks[index]
    if len(stack) == 0 {
        return -1
    }
    val := stack[len(stack)-1]
    s.stacks[index] = stack[:len(stack)-1]
    // 子栈弹空后移除
    if len(s.stacks[index]) == 0 {
        s.stacks = append(s.stacks[:index], s.stacks[index+1:]...)
    }
    return val
}

相似题目

题目	难度	考察点
155. 最小栈	中等	栈、设计
232. 用栈实现队列	简单	栈、设计
225. 用队列实现栈	简单	队列、设计
1381. 设计一个支持增量操作的栈	中等	栈、设计
面试题 03.01. 三合一	简单	数组、设计
面试题 03.02. 栈的最小值	简单	栈、设计

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/42495272