406. Reconstruct the queue according to height

Topic link
analysis ： The title means that we should put an array people[i] = {h,k}, Put it in one place , And can guarantee , There is k individual h Greater than or equal to the current h Of .
First, let's talk about the variables that need to be used ：

res[][]： A two-dimensional array used to record the final answer
vis[]： It is used to record whether the element has been placed in this position
count： It is used to record the number of previous ones greater than or equal to the current h The elements of

Then we can think the other way around , First find the smallest h, So the others h It must be bigger than now , Then we only need to consider the following k Just one position , in other words , Currently, this is placed in the k+1 Just one position .（ And here for simplicity , I didn't consider having the same h）

Now let's consider the same h The situation of .
In fact, it's also very easy to consider .
We from res Of the 0 Start traversing , When count Less than k When , Then it means that we need to continue to traverse later , Because I haven't found the right place yet .
So when count Self increasing , in other words , When can I find a greater than or equal to the current h The location of ？
First of all ： Traverse to the current location without being accessed , Because every time we need to take out people The smallest remaining , therefore , Those that have not been accessed must be placed behind the elements , So it must be greater than or equal to the current h Of , here count+1.
second ： Traverse to the element equal to the current h, That is, there are the same h Existing situation , At this time, too count+1.

until People It's all there res that will do .

Then there are two more questions
Question 1 ： It's how we find it every time h The smallest ？
Question two ： And if the current remaining people The smallest of all h There are many. , Which one to choose ？

Question 1 ：
We can people Put it in the small top pile , So every time you get h The smallest .
Question two ：
If h identical , So we should choose k The smallest , because h identical ,k The smallest must be in front .

Code ：

class Solution {
    
    public int[][] reconstructQueue(int[][] people) {
    
        // Small cap pile  h Put the small one on it , h The same thing k Put the small one on it 
        Queue<int[]> queue = new PriorityQueue<>((i1,i2)->{
    
            if(i1[0]!=i2[0]){
    
                return i1[0]-i2[0];
            }else{
    
                return i1[1]-i2[1];
            }
        });

        int n = people.length;
        int[][] res = new int[n][2];
        // Record whether this location has been visited 
        boolean[] vis = new boolean[n];
        for(int i=0; i<n; i++){
    
            queue.offer(people[i]);
        }
        while(!queue.isEmpty()){
    
            int[] top = queue.poll();
            int count=0;
            int i=0;
            while(i<n && count<top[1]){
    
                // This location has not been visited   perhaps   This location has been visited , however h equal 
                if(!vis[i] || res[i][0]==top[0]){
    
                    count++;
                }
                i++;
            }
            while(vis[i]){
    
                i++;
            }
            res[i] = top;
            vis[i] = true;
        }
        return res;
    }
}