LeetCode题解：1051. 高度检查器，JavaScript，桶排序，详细注释

[chencl1986]

原题链接：https://leetcode-cn.com/problems/height-checker/

解题思路：

参考了O(n)解法，用时与内存击败100% java用户、简单的桶排序。

/**
 * @param {number[]} heights
 * @return {number}
 */
var heightChecker = function (heights) {
  // 创建一个桶，index对应0-100的数值，其值代表它出现的次数
  let bucket = new Array(101).fill(0);

  // 遍历heights，对heights中所有值进行计数
  // 例如heights为[1, 1, 4, 2, 1, 3]，即可计算出其中有3个1，1个2，1个3，1个4
  for (let i = 0; i < heights.length; i++) {
    bucket[heights[i]]++;
  }

  // 统计最终未正常排序的结果
  let count = 0;

  // 按顺序遍历桶，相当于按顺序遍历了排序好的heights
  for (let i = 1, j = 0; i < bucket.length; i++) {
    // 每遍历到一个bucket[i]大于0，即为i还有数量，就将其值进行循环，
    while (bucket[i] > 0) {
      // 如果此时heights[j]的值与i的值不同，则表示该值未正确排序，即count++
      if (heights[j] !== i) {
        count++;
      }
      // 每次循环bucket[i]减1，表示i的数量减少1个
      bucket[i]--;
      // 每次i减1，都将heights数组的index加1，即j++
      j++;
    }
  }

  return count;
};