406. Queue Reconstruction by Height

Leetcode 问题: 406. Queue Reconstruction by Height
Categories:
Tags:

题目

You are given an array of people, people, which are the attributes of some people in a queue (not necessarily in order). Each people[i] = [hi, ki] represents the ith person of height hi with exactly ki other people in front who have a height greater than or equal to hi.

Reconstruct and return the queue that is represented by the input array people. The returned queue should be formatted as an array queue, where queue[j] = [hj, kj] is the attributes of the jth person in the queue (queue[0] is the person at the front of the queue).

给予一个使用者阵列，阵列中包含每个 使用者的身高 以及 使用者希望排队前面有多少人 跟他一样高或比他高

例如：[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]

阵列 身高 希望有多少人跟他一样高或比他高
[7,0] 7 0
[4,4] 4 4
[7,1] 7 1
[5,0] 5 0
[6,1] 6 1
[5,2] 5 2

目标要找到符合所有人的 身高排序 以及 希望的前方障碍物

[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] 最后排序

索引顺序 1 2 3 4 5 6
使用者 [5,0] [7,0] [5,2] [6,1] [4,4] [7,1]
使用者身高 5 7 5 6 4 7
前面有多少人跟他一样高或比他高 0 0 2 1 4 1

Example

Input: people = [[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]]
Explanation:
Person 0 has height 5 with no other people taller or the same height in front.
Person 1 has height 7 with no other people taller or the same height in front.
Person 2 has height 5 with two persons taller or the same height in front, which is person 0 and 1.
Person 3 has height 6 with one person taller or the same height in front, which is person 1.
Person 4 has height 4 with four people taller or the same height in front, which are people 0, 1, 2, and 3.
Person 5 has height 7 with one person taller or the same height in front, which is person 1.
Hence [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] is the reconstructed queue.

Input: people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
Output: [[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

答案

  1. 将身高由 高到低排序，若身高相同，前面 需要比他高的人越少 排越前面
  2. 因为使用者阵列是按照身高排序，所以越前面的人身高越高，越没有阻碍，「后面的使用者」身高会低于或等于「前面的使用者」，看那个使用者前面需要多少阻碍，将他安排在指定的位置

JavaScript

/**
 * @param {number[][]} peopleList
 * @return {number[][]}
 */
var reconstructQueue = function(peopleList) {
    if (!peopleList || peopleList.length == 0 || peopleList[0].length == 0) {
        // 如果没有传入人的阵列资料
        return [];
    }

    // 排序身高大小(身高越高排前面)
    peopleList.sort((a, b) => {
        if (a[0] > b[0]) {
            // 当 a[0] 数字比 b[0] 大，a 较大排前面
            return -1;
        } else if (a[0] < b[0]) {
            // 当 a[0] 数字比 b[0] 小，a 较笑排后面
            return 1;
        } else {
            // a[0] 数字 与 b[0] 一样大，表示身高一样，将前面阻碍需要越少的放前面
            if (a[1] < b[1]) {
                // 当 a[1] 数字比 b[0] 小，a 需要较少人比他高，a 排前面
                return -1;
            } else {
                // 当 a[1] 数字比 b[0] 大，a 需要较多人比他高，a 排后面
                return 1;
            }
        }
    });

    // 排序的使用者清单
    let orderPeopleList = [];

    peopleList.forEach((currentPeople) => {
        // 目前使用者，前面允许多少人身高「跟他一样或比他高」
        let currentPeopleAllowHigherPeopleCount = currentPeople[1];
        // 因为使用者阵列是按照身高排序，所以越前面的人身高越高，越没有阻碍
        // 「后面的使用者」身高会低于或等于「前面的使用者」，看那个使用者前面需要多少阻碍，将他安排在指定的位置
        orderPeopleList.splice(currentPeopleAllowHigherPeopleCount, 0, currentPeople);
    });

    return orderPeopleList;
};

参考资料