LeetCode 1172. 餐盘栈

Categories:

题目描述
思路分析
1. 解法一：多栈 + 小根堆（推荐）
相似题目

题目描述

✅ 1172. 餐盘栈

思路分析

解法一：多栈 + 小根堆（推荐）

核心思路：

用数组维护多个栈，容量固定。

小根堆记录还有空位的栈下标，确保 push 总是填左侧最小可用栈。

pop 从最右侧非空栈弹出，并动态收缩右边界。

复杂度分析：

时间复杂度：O(log n)，每次 push/popAtStack 维护堆。

空间复杂度：O(n)，用于存储所有元素与堆。

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

class DinnerPlates {
    private final int capacity;
    private final List<List<Integer>> stacks = new ArrayList<>();
    private final PriorityQueue<Integer> available = new PriorityQueue<>();

    public DinnerPlates(int capacity) {
        this.capacity = capacity;
    }

    public void push(int val) {
        while (!available.isEmpty()) {
            int idx = available.peek();
            if (idx < stacks.size() && stacks.get(idx).size() < capacity) {
                break;
            }
            available.poll();
        }

        if (available.isEmpty()) {
            List<Integer> stack = new ArrayList<>();
            stack.add(val);
            stacks.add(stack);
            if (capacity > 1) {
                available.offer(stacks.size() - 1);
            }
        } else {
            int idx = available.peek();
            stacks.get(idx).add(val);
            if (stacks.get(idx).size() == capacity) {
                available.poll();
            }
        }
    }

    public int pop() {
        int idx = stacks.size() - 1;
        while (idx >= 0 && stacks.get(idx).isEmpty()) {
            stacks.remove(idx);
            idx--;
        }
        if (idx < 0) {
            return -1;
        }

        int val = stacks.get(idx).remove(stacks.get(idx).size() - 1);
        available.offer(idx);
        return val;
    }

    public int popAtStack(int index) {
        if (index < 0 || index >= stacks.size() || stacks.get(index).isEmpty()) {
            return -1;
        }

        int val = stacks.get(index).remove(stacks.get(index).size() - 1);
        available.offer(index);
        return val;
    }
}

import "container/heap"

type DinnerPlates struct {
	capacity int
	stacks   [][]int
	avail    IntHeap
}

func Constructor(capacity int) DinnerPlates {
	return DinnerPlates{capacity: capacity, stacks: make([][]int, 0), avail: IntHeap{}}
}

func (d *DinnerPlates) push(val int) {
	for d.avail.Len() > 0 {
		idx := d.avail[0]
		if idx < len(d.stacks) && len(d.stacks[idx]) < d.capacity {
			break
		}
		heap.Pop(&d.avail)
	}

	if d.avail.Len() == 0 {
		d.stacks = append(d.stacks, []int{val})
		if d.capacity > 1 {
			heap.Push(&d.avail, len(d.stacks)-1)
		}
	} else {
		idx := d.avail[0]
		d.stacks[idx] = append(d.stacks[idx], val)
		if len(d.stacks[idx]) == d.capacity {
			heap.Pop(&d.avail)
		}
	}
}

func (d *DinnerPlates) pop() int {
	for len(d.stacks) > 0 && len(d.stacks[len(d.stacks)-1]) == 0 {
		d.stacks = d.stacks[:len(d.stacks)-1]
	}
	if len(d.stacks) == 0 {
		return -1
	}

	idx := len(d.stacks) - 1
	stack := d.stacks[idx]
	val := stack[len(stack)-1]
	d.stacks[idx] = stack[:len(stack)-1]
	heap.Push(&d.avail, idx)
	return val
}

func (d *DinnerPlates) popAtStack(index int) int {
	if index < 0 || index >= len(d.stacks) || len(d.stacks[index]) == 0 {
		return -1
	}

	stack := d.stacks[index]
	val := stack[len(stack)-1]
	d.stacks[index] = stack[:len(stack)-1]
	heap.Push(&d.avail, index)
	return val
}

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

相似题目

题目	难度	考察点
1172. 餐盘栈	困难	堆、数据结构
155. 最小栈	简单	栈
225. 用队列实现栈	简单	栈
716. 最大栈	困难	栈、堆
895. 最大频率栈	困难	栈、哈希

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/73576461