【leetcode】406.根据身高重建队列 （贪心算法，java实现）

406. 根据身高重建队列

难度中等442

假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。

注意：
总人数少于1100人。

示例

输入:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

输出:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

方法：贪心算法

这个问题是让我们重建队列。

让我们从最简单的情况下思考，当队列中所有人的 (h,k) 都是相同的高度 h，只有 k 不同时，解决方案很简单：每个人在队列的索引 index = k。

即使不是所有人都是同一高度，这个策略也是可行的。因为个子矮的人相对于个子高的人是 “看不见” 的，所以可以先安排个子高的人。

上图中我们先安排身高为 7 的人，将它放置在与 k 值相等的索引上；再安排身高为 6 的人，同样的将它放置在与 k 值相等的索引上。

该策略可以递归进行：

• 将最高的人按照 k 值升序排序，然后将它们放置到输出队列中与 k 值相等的索引位置上。

• 按降序取下一个高度，同样按 k 值对该身高的人升序排序，然后逐个插入到输出队列中与 k 值相等的索引位置上。

• 直到完成为止。
  
  
  
  
  
  
  
  
  
  

  整体思路：

  1. 先按身高降序排序，相同身高按k升序排序，经过此次排序后高的人一定在矮的人的前面并且相同高度的人的相对顺序就是最终结果的相对顺序。请记住这两点，敲黑板
  2. 创建一个集合，这个集合的每个元素是一个一维数组，也就是我们二维数组的一行。
  3. 以行为单位遍历排好序的people[][]数组，假设每行数据是p[], 把每行元素插入到集合的索引为p[1]的位置，
  4. 把集合中的数据转换为一个二维数组，返回即是正确结果

  下面解释为什么经过第三步后就达到了我们题目要求的输出结果：

  经过第一步排序后高的人一定在矮的人的前面并且相同高度的人的相对顺序就是最终结果的相对顺序，所以 在进行第三步的过程中，高的人的数据肯定是先被存入集合的，所以每当我们取出一行数据，集合中已有的元素的身高肯定都是大于等于当前元素的身高的，所以当我们取出p[]数组后，发现前面应该有p[1]个人比自己高或者高度和自己相同，那么当前元素就应该排在集合的p[1]下标的位置(仔细想想是不是)，好比说目前有一个队列的人，这些人要么比你高，要么和你一样高，现在要你插入入队中，保证你前面有p[1]个人的身高大于等于你，你是不是应该排在索引为p[1]的位置

  所以经过第三步的插入操作后，把每个人都插入到了正确的位置，所以根据这个集合转换的二维数组当然就是正确结果了。

  算法：

• 排序：

  • 按高度降序排列。
  • 在同一高度的人中，按 k 值的升序排列。

• 逐个地把它们放在输出队列中，索引等于它们的 k 值。

• 返回输出队列

class Solution {
  public int[][] reconstructQueue(int[][] people) {
    Arrays.sort(people, new Comparator<int[]>() {
      @Override
      public int compare(int[] o1, int[] o2) {
        // if the heights are equal, compare k-values
        return o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0];
      }
    });
	//Arrays.sort(people, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]);
    List<int[]> output = new LinkedList<>();
    for(int[] p : people){
      output.add(p[1], p);
    }

    int n = people.length;
    return output.toArray(new int[n][2]);
  }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(N^2)$、。排序使用了 $\mathcal{O}(N\log N)$的时间，每个人插入到输出队列中需要 O(k) 的时间，其中 k 是当前输出队列的元素个数。总共的时间复杂度为 $\mathcal{O}\left(\sum _{k=0}^{N-1}k\right)$
  O(k) 的时间，其中 k 是当前输出队列的元素个数。总共的时间复杂度为 $\mathcal{O}\left(\sum _{k=0}^{N-1}k\right)$
• 空间复杂度：O(N)，输出队列使用的空间。