406. Queue Reconstruction by Height（根据身高重排队列）

Myth丶恋晨 2022-07-15 08:07 142阅读 0赞

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers `(h, k)`, where `h` is the height of the person and `k` is the number of people in front of this person who have a height greater than or equal to `h`. Write an algorithm to reconstruct the queue.

Note:  
The number of people is less than 1,100.

Example

Input:
    [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
    
    Output:
    [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

题目大意：重排一个由人站成的队列，使其遵循规律：对于每一个表示 人 的元素（h，k），h代表这个人的身高，k代表站在他前面，且身高不低于他的人数。

题目思路：贪心算法。每次确定当前队列的第一个人，当前队列的第一个人满足（a，b），其中b=0，a为**当前队列里面**所有（h，k）中**k=0**的最小 **h**值。确定当前队列的第一个人后，对 除去这个人后的新队列 进行上述操作，从而得到新队列的第一个人 即为 总队列的第二个人 ...重复上述步骤，便得到满足条件的队列。代码如下：（87ms，beats 25.73%）

public int[][] reconstructQueue(int[][] people) {
    		int m = people.length, i, j, k, min = Integer.MAX_VALUE, minIndex = 0;
    		int[][] temps = new int[m][2]; //由people数组复制得来，对这个数组进行操作
    		int[] index = new int[m]; //记录最后的结果顺序
    		boolean[] visited = new boolean[m]; //记录哪些元素已经被确定了位置
    		for (i = 0; i < m; i++) {
    			visited[i] = false;
    			temps[i][0] = people[i][0];
    			temps[i][1] = people[i][1];
    		}
    		for (i = 0; i < m; i++, min = Integer.MAX_VALUE) {
    			for (j = 0; j < m; j++) {
    				//寻找当前队列所有(h，k)中k=0，h最小的元素
    				if (visited[j] == false && temps[j][1] == 0) {
    					if (people[j][0] < min) {
    						min = people[j][0];
    						minIndex = j; //记录位置
    					}
    				}
    			}
    			visited[minIndex] = true;
    			index[i] = minIndex;
    			for (k = 0; k < m; k++) {
    				if (visited[k] == false && temps[k][0] <= min) {
    					temps[k][1]--;
    				}
    			}
    		}
    		for (i = 0; i < m; i++) {
    			temps[i][0] = people[index[i]][0];
    			temps[i][1] = people[index[i]][1];
    		}
    		return temps;
    	}