二分

若$h_m > h_s$，且$h_m$是满足h指数，则$h_s$也满足h指数。

$h$越小，越能满足h指数。这就是单调性

• 题意可得，h最大是n，最小是0

时间复杂度$O(NlogN)$，空间复杂度$O(1)$

AC代码

class Solution {
public:
    bool check(vector<int>& cita, int h) {
        int cnt = 0;
        for (auto x : cita) {
            if (x >= h)
                cnt ++;
            if (cnt >= h)
                return true;
        }
        return false;
    }

    int hIndex(vector<int>& cita) {
        int n = cita.size();
        int l = 0 ,r = n;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (check(cita, mid)) l = mid;
            else r = mid - 1;
        }
        return l;

    }
};