# LeetCode 1051. Height Checker

https://leetcode.com/problems/height-checker/description/

## 題目大意

有一堆學生，你希望他們依照身高以非遞減的方式排好
現在，給你學生們的身高，請問離排好隊還有幾個人位置不對？

Constraints:

- $1 \le$ `heights.length` $\le 100$
- $1 \le$ `heights[i]` $\le 100$

## 思考

### Algo 1

你就排好比比看就好

class Solution
{
public:
    int heightChecker(vector<int> &heights)
    {
        vector<int> temp = heights;
        sort(temp.begin(), temp.end());
        const int n = temp.size();
        int ans = 0;

        for (int i = 0; i < n; ++i)
        {
            if (temp[i] != heights[i])
                ++ans;
        }

        return ans;
    }
};

### Algo 2

我們用一個 `cur` 紀錄身高比到多高

先記錄每種身高的出現頻率

只要 `cur` 這個身高還沒出現過，就一直往上加， `cur` 就能隨預期的排序方式增長

class Solution
{
public:
    int heightChecker(vector<int> &heights)
    {
        int ans = 0, cur = 1;
        array<int, 101> cnt;

        for (const int height : heights)
        {
            ++cnt[height];
        }

        for (const int height : heights)
        {
            while (!cnt[cur])
                ++cur;

            if (height != cur)
                ++ans;

            --cnt[cur];
        }

        return ans;
    }
};

每次比完就要把理想隊伍往前走，所以 `--cnt[cur]`