1172. The plate stack has a sequence table + stack

1172. Plate stack

We put an infinite number ∞ In a row , From left to right 0 Numbered starting . The maximum capacity of each stack  capacity  All the same .

Realize a call 「 Dinner plate 」 Class  DinnerPlates：

• DinnerPlates(int capacity) - Give the maximum capacity of the stack  capacity.
• void push(int val) - The positive integer that will be given  val  push   The first one from left to right   There is no full stack .
• int pop() - return   The first one from right to left   The value at the top of the non empty stack , And remove it from the stack ; If all stacks are empty , Please return  -1.
• int popAtStack(int index) - Return number  index  The value at the top of the stack , And remove it from the stack ; If the number  index  The stack of is empty , Please return  -1.

Example ：

 Input ： 
["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],[],[],[],[],[]]
 Output ：
[null,null,null,null,null,null,2,null,null,20,21,5,4,3,1,-1]

 explain ：
DinnerPlates D = DinnerPlates(2);  //  initialization , Maximum stack capacity  capacity = 2
D.push(1);
D.push(2);
D.push(3);
D.push(4);
D.push(5);         //  The status quo of the stack is ：   2  4
                                    1  3  5
                                    ﹈ ﹈ ﹈
D.popAtStack(0);   //  return  2. The status quo of the stack is ：    4
                                          1  3  5
                                          ﹈ ﹈ ﹈
D.push(20);        //  The status quo of the stack is ：  20 4
                                   1  3  5
                                   ﹈ ﹈ ﹈
D.push(21);        //  The status quo of the stack is ：  20 4  21
                                   1  3  5
                                   ﹈ ﹈ ﹈
D.popAtStack(0);   //  return  20. The status quo of the stack is ：     4  21
                                            1  3  5
                                            ﹈ ﹈ ﹈
D.popAtStack(2);   //  return  21. The status quo of the stack is ：     4
                                            1  3  5
                                            ﹈ ﹈ ﹈ 
D.pop()            //  return  5. The status quo of the stack is ：       4
                                            1  3 
                                            ﹈ ﹈  
D.pop()            //  return  4. The status quo of the stack is ：    1  3 
                                           ﹈ ﹈   
D.pop()            //  return  3. The status quo of the stack is ：    1 
                                           ﹈   
D.pop()            //  return  1. There is no stack now .
D.pop()            //  return  -1. There is still no stack .

Tips ：

• 1 <= capacity <= 20000
• 1 <= val <= 20000
• 0 <= index <= 100000
• At most  push,pop, and  popAtStack  Conduct  200000  Secondary call .

Tips ：

1 <= capacity <= 20000
1 <= val <= 20000
0 <= index <= 100000
At most push,pop, and popAtStack Conduct 200000 Secondary call .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/dinner-plate-stacks
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

The result of doing the question

success , But at first, I didn't understand the question , I made mistakes several times before I understood

  Method 1： Ordered set + Array stack （ full + empty + part ）

1. The stack is initially put into the array , Probably establish 200000 A length is enough .

2. It is processed in three stacks ：

•         Full stack , If the element is full, you can put it on this stack , No entry or exit
•         Partial stack , Put some elements on this stack instead of empty , In and out
•         Empty stack , Those without elements are put on this stack , No entry, no exit , Initially, all elements are put into this stack

3. Fill in the process ： Take the smaller of partial stack and empty stack id fill , Remove from the empty stack , If full, enter full stack , Otherwise, enter part of the stack

4. Take out the top of the stack ： No full stack, partial stack returns -1, Take the largest part of the stack and the full stack id, Remove from the full stack , If empty, enter the empty stack , Otherwise, enter part of the stack

5. Take out the specified id: If not filled, return -1, Remove this... From the full stack and part of the stack id, If empty, enter the empty stack , Otherwise, enter part of the stack

class DinnerPlates {
        final int MAX = 200000;
   Stack<Integer>[] stacks = new Stack[MAX+1];
   TreeSet<Integer> waitUse = new TreeSet<>();
   TreeSet<Integer> partUse = new TreeSet<>();
   TreeSet<Integer> fullUse = new TreeSet<>();
   int capacity;
    public DinnerPlates(int capacity) {
        this.capacity = capacity;
       for(int i = 0; i < MAX+1; i++){
           waitUse.add(i);
       }
    }
    
    public void push(int val) {
        int first = partUse.isEmpty()?waitUse.first():Math.min(partUse.first(),waitUse.first());
        if(stacks[first]==null) stacks[first] = new Stack<>();
        stacks[first].push(val);
        waitUse.remove(first);
        partUse.remove(first);
        if(stacks[first].size()!=capacity) partUse.add(first);
        else fullUse.add(first);
    }
    
    public int pop() {
        int a = fullUse.isEmpty()?-1:fullUse.last();
        int b = partUse.isEmpty()?-1:partUse.last();
        return popAtStack(Math.max(a,b));
    }
    
    public int popAtStack(int index) {
        if(index == -1 || stacks[index]==null||stacks[index].isEmpty()) return -1;
        fullUse.remove(index);
        partUse.remove(index);
        int v = stacks[index].pop();
        if(stacks[index].isEmpty()) waitUse.add(index);
        else partUse.add(index);
        return v;
    }

}

  Method 2： Ordered set + Set stack ( full + empty + part Lazy loading )

1. For the method 1 The stack in , You don't have to initialize everything at first .

2. When filling in, the empty stack is empty , Just initialize a stack top , This can save more space .

3. At first, the array will be full of space , There is too much waste in , You can use sets , Reduce overall space consumption

class DinnerPlates {
   List<Stack<Integer>> stacks = new ArrayList<>();
   TreeSet<Integer> waitUse = new TreeSet<>();
   TreeSet<Integer> partUse = new TreeSet<>();
   TreeSet<Integer> fullUse = new TreeSet<>();
   int capacity;
    public DinnerPlates(int capacity) {
        this.capacity = capacity;
    }
    
    public void push(int val) {
        if(waitUse.isEmpty()) {
            waitUse.add(stacks.size());
            stacks.add(new Stack<>());
        }
        int first = partUse.isEmpty()?waitUse.first():Math.min(partUse.first(),waitUse.first());
        stacks.get(first).push(val);
        waitUse.remove(first);
        partUse.remove(first);
        if(stacks.get(first).size()!=capacity) partUse.add(first);
        else fullUse.add(first);
    }
    
    public int pop() {
        int a = fullUse.isEmpty()?-1:fullUse.last();
        int b = partUse.isEmpty()?-1:partUse.last();
        return popAtStack(Math.max(a,b));
    }
    
    public int popAtStack(int index) {
        if(index == -1 || index>=stacks.size() || stacks.get(index).isEmpty()) return -1;
        fullUse.remove(index);
        partUse.remove(index);
        int v = stacks.get(index).pop();
        if(stacks.get(index).isEmpty()) waitUse.add(index);
        else partUse.add(index);
        return v;
    }

}

Method 3： Ordered set + Set stack ( Fill the stack and take out the stack Lazy loading )

1. Except for the division of three stacks , It can also be divided into two overlapping stacks .

2. Fill the stack ： Empty and partial can be put into the filling stack

3. Remove the stack ： Part and full can be put into and taken out of the stack

4. Fill in the process ： If the fill stack is empty, add a new element , Take out the minimum id, Fill in , Add and remove stack ; If so id Stack full , Then remove from the fill stack

5. Removal process ： If the stack element is not taken out , return -1, Take out the minimum id, Take out , And add filling stack ; If so id The stack is empty , Remove from the fetch stack

6. Take out id: If the fetch stack does not exist , Then return to -1; Take out an element , Put it on the filling stack ; If empty, remove from the fetch stack

class DinnerPlates {
   List<Stack<Integer>> stacks = new ArrayList<>();
   TreeSet<Integer> pushUse = new TreeSet<>();
   TreeSet<Integer> popUse = new TreeSet<>();
   int capacity;
    public DinnerPlates(int capacity) {
        this.capacity = capacity;
    }
    
    public void push(int val) {
        if(pushUse.isEmpty()) {
            pushUse.add(stacks.size());
            stacks.add(new Stack<>());
        }
        int first = pushUse.first();
        stacks.get(first).push(val);
        popUse.add(first);
        
        if(stacks.get(first).size()==capacity) pushUse.remove(first);
    }
    
    public int pop() {
        if(popUse.isEmpty()) return -1;
        int last = popUse.last();
        int v = stacks.get(last).pop();
        pushUse.add(last);
        if(stacks.get(last).isEmpty()) popUse.remove(last);
        return v;
    }
    
    public int popAtStack(int index) {
        if(index>=stacks.size() || stacks.get(index).isEmpty()) return -1;
        int v = stacks.get(index).pop();
        pushUse.add(index);
        if(stacks.get(index).isEmpty()) popUse.remove(index);
        return v;
    }

}