1051.高度检查器

1051. 高度检查器

学校在拍年度纪念照时,一般要求学生按照 非递减 的高度顺序排列。

请你返回至少有多少个学生没有站在正确位置数量。该人数指的是:能让所有学生以 非递减 高度排列的必要移动人数。

示例:

输入:[1,1,4,2,1,3]

输出:3

解释:

高度为 4、3 和最后一个 1 的学生,没有站在正确的位置。

提示:

1 <= heights.length <= 100

1 <= heights[i] <= 100


思路:普通人的思路应该是把原数组排序一遍,然后再比较位置,但是排序的复杂度是On2,能不能On就把题目解出来呢,我的考虑是,因为只要找出站错学生,并记录数量就好了,假设有个“哨兵”从左向右移动,哨兵会每次移动到比之前大的那个位置,遇到比之前小的数那就是站错的同学

然而我发现这个思路是错的,这样只能找出一部分站错的位置,最后我还是老老实实的排序再比较!

提交记录:https://leetcode-cn.com/submissions/detail/21704153/