406. Queue Reconstruction by Height

 一刷 06/2022

Version #2 Sorting

看了答案发现max heap完全没有必要

可以直接sort

Time O(N^2)

Space O(1)

Runtime: 10 ms, faster than 66.77% of Java online submissions for Queue Reconstruction by Height.

Memory Usage: 54.5 MB, less than 60.13% of Java online submissions for Queue Reconstruction by Height.

class Solution {

    public int[][] reconstructQueue(int[][] people) {

        Arrays.sort(people, (a, b) -> a[0] == b[0] ? Integer.compare(a[1], b[1]) : Integer.compare(b[0], a[0]));

        List<int[]> que = new ArrayList<>();

        for (int[] person : people) {

            que.add(person[1], person);

        }

        return que.toArray(new int[0][]);

    }

}

Version #1 Max Heap

Reconstruct from highest height to lowest

Time O(N^2logN)

Space O(N)

Runtime: 9 ms, faster than 77.17% of Java online submissions for Queue Reconstruction by Height.

Memory Usage: 55.3 MB, less than 6.65% of Java online submissions for Queue Reconstruction by Height.

class Solution {

    public int[][] reconstructQueue(int[][] people) {

        // insert shorter people in front of taller people will not influence the taller people's k value

        // So we should have a max heap that pops out tallest people to shortest people

        // If two people have the same height, the one with smaller k value should be polled out first

        Queue<int[]> maxHeap = new PriorityQueue<>((a, b) -> {

            if (a[0] != b[0]) {

                return Integer.compare(b[0], a[0]); // larger number has higher priority

            }

            return Integer.compare(a[1], b[1]);

        });

        for (int[] person : people) {

            maxHeap.offer(person);

        }

        List<int[]> que = new ArrayList<>();

        while (!maxHeap.isEmpty()) {

            int[] curr = maxHeap.poll();

            que.add(curr[1], curr);

        }

        return que.toArray(new int[0][]);

    }

}