JavaInterview JavaInterview
首页
指南
分类
标签
归档
  • CSDN (opens new window)
  • 文档集合 (opens new window)
  • 系统架构 (opens new window)
  • 微信号 (opens new window)
  • 公众号 (opens new window)

『Java面试+Java学习』
首页
指南
分类
标签
归档
  • CSDN (opens new window)
  • 文档集合 (opens new window)
  • 系统架构 (opens new window)
  • 微信号 (opens new window)
  • 公众号 (opens new window)
  • 指南
  • 简历

  • Java

  • 面试

  • 算法

  • algorithm
  • leetcode
JavaInterview.cn
2023-02-21
目录

餐盘栈Java

文章发布较早,内容可能过时,阅读注意甄别。

# 题目

我们把无限数量 ∞ 的栈排成一行,按从左到右的次序从 0 开始编号。每个栈的的最大容量 capacity 都相同。

实现一个叫「餐盘」的类 DinnerPlates:

  • DinnerPlates(int capacity) - 给出栈的最大容量 capacity。
  • void push(int val) - 将给出的正整数 val 推入 从左往右第一个 没有满的栈。
  • int pop() - 返回 从右往左第一个 非空栈顶部的值,并将其从栈中删除;如果所有的栈都是空的,请返回 -1。
  • int popAtStack(int index) - 返回编号 index 的栈顶部的值,并将其从栈中删除;如果编号 index 的栈是空的,请返回 -1。

示例:

输入: 
["DinnerPlates","push","push","push","push","push","popAtStack","push","push","popAtStack","popAtStack","pop","pop","pop","pop","pop"]
[[2],[1],[2],[3],[4],[5],[0],[20],[21],[0],[2],[],[],[],[],[]]
输出:
[null,null,null,null,null,null,2,null,null,20,21,5,4,3,1,-1]

解释:
DinnerPlates D = DinnerPlates(2);  // 初始化,栈最大容量 capacity = 2
D.push(1);
D.push(2);
D.push(3);
D.push(4);
D.push(5);         // 栈的现状为:    2  4
                                    1  3  5
                                    ﹈ ﹈ ﹈
D.popAtStack(0);   // 返回 2。栈的现状为:      4
                                          1  3  5
                                          ﹈ ﹈ ﹈
D.push(20);        // 栈的现状为:  20  4
                                   1  3  5
                                   ﹈ ﹈ ﹈
D.push(21);        // 栈的现状为:  20  4 21
                                   1  3  5
                                   ﹈ ﹈ ﹈
D.popAtStack(0);   // 返回 20。栈的现状为:       4 21
                                            1  3  5
                                            ﹈ ﹈ ﹈
D.popAtStack(2);   // 返回 21。栈的现状为:       4
                                            1  3  5
                                            ﹈ ﹈ ﹈ 
D.pop()            // 返回 5。栈的现状为:        4
                                            1  3 
                                            ﹈ ﹈  
D.pop()            // 返回 4。栈的现状为:    1  3 
                                           ﹈ ﹈   
D.pop()            // 返回 3。栈的现状为:    1 
                                           ﹈   
D.pop()            // 返回 1。现在没有栈。
D.pop()            // 返回 -1。仍然没有栈。

提示:

  • 1 <= capacity <= 20000
  • 1 <= val <= 20000
  • 0 <= index <= 100000
  • 最多会对 push,pop,和 popAtStack 进行 200000 次调用。

# 思路

PriorityQueue q;

# 解法


class DinnerPlates {

    final int N = (int) 5e5+10;
    int[][] stacks;
    int[] idxs;
    int sIdx;
    int capa;
    PriorityQueue<Integer> q;

    public DinnerPlates(int capacity) {
        this.capa = capacity;
        capacity++;
        stacks = new int[N/capacity][capacity];
        idxs = new int[N];
        q = new PriorityQueue();
    }

    public void push(int val) {
        while(idxs[sIdx] == capa)sIdx++;
        while (!q.isEmpty()){//存在前方未满的栈
            int idx = q.poll();
            stacks[idx][idxs[idx]++] = val;
            return;
        }
        stacks[sIdx][idxs[sIdx]++] = val;
        while(idxs[sIdx] == capa)sIdx++;
    }

    public int pop() {
        while( sIdx >= 0 && idxs[sIdx] == 0)sIdx--;
        if(sIdx < 0)return -1;
        int t = stacks[sIdx][--idxs[sIdx]];
        q.add(sIdx);
        return t;
    }

    public int popAtStack(int index) {
        if(idxs[index] == 0)return -1;
        int t = stacks[index][--idxs[index]];
        q.add(index);
        return t;

    }
}

/**
 * Your DinnerPlates object will be instantiated and called as such:
 * DinnerPlates obj = new DinnerPlates(capacity);
 * obj.push(val);
 * int param_2 = obj.pop();
 * int param_3 = obj.popAtStack(index);
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

# 总结

  • 分析出几种情况,然后分别对各个情况实现
微信 支付宝
最近更新
01
1637. 两点之间不包含任何点的最宽垂直区域 Java
06-26
02
1636. 按照频率将数组升序排序 Java
06-26
03
1638. 统计只差一个字符的子串数目 Java
06-26
更多文章>
Theme by Vdoing | Copyright © 2019-2025 JavaInterview.cn
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式