H 指数 II 图解题解

这道题到底在问什么

输入

[0,1,3,5,6]

输出

3

先想最直接的笨办法

笨办法谁都会：从引用最多的论文往回数，数到「凑不齐这么多篇都达标」就停。但百万篇论文就慢了。题目特意给了「升序」，就是在提示——能二分。（动画第 3 步）

最优解：一步一步想明白

1. 3笨办法谁都会：从引用最多的论文往回数，数到「凑不齐这么多篇都达标」就停。但百万篇论文就慢了。题目特意给了「升序」，就是在提示——能二分。
2. 4这是全题的命根子。站在下标 mid 上往右看：右边(含自己)有 n−mid 篇，它们的引用全都 ≥ citations[mid](升序保证)。于是只要 citations[mid] ≥ n−mid，这 n−mid 篇就同时满足「各自 ≥ (n−mid) 次」——h 至少能到 n−mid。
3. 5我们其实在找最靠左的那个达标起点：从它到末尾的论文数就是 h。盯住下面 lo/hi/mid 三根指针，看 citations[mid] 和 n−mid 一比，区间怎么一刀刀收缩。最后答案 = n − lo。
4. 6下标 2 到末尾共 5−2=3 篇先把「n−mid」这个量看明白。站在下标 2 上，紫底窗口框住的就是它到末尾的 3 篇(引用 3、5、6)。因为升序，这 3 篇每一篇都 ≥ citations[2]=3。
5. 7下标 3 到末尾共 5−3=2 篇再往右挪到下标 3：窗口缩成2 篇(引用 5、6)。下标越往右，n−mid 越小，但门槛 citations[mid] 越高——这一升一降之间，存在一个最佳平衡点，二分要找的就是它。
6. 8下标 0 到末尾共 5−0=5 篇退到最左下标 0：窗口张到全部 5 篇，可门槛塌到 0——想让 5 篇都 ≥5 次根本办不到。起点太靠左，篇数虽多却没人达标。二分要在「篇数」和「门槛」之间挑出最甜的那个点。
7. 9lo=0, hi=n−1=4正式开二分。lo 指数组头(下标 0)、hi 指数组尾(下标 4)。我们要在 [lo,hi] 里夹出那个最靠左的达标起点，循环用 lo ≤ hi，结束时答案 = n − lo。
8. 10mid = (0+4)/2 = 2取中点 mid=(0+4)/2=2。接下来要比的是 citations[mid] 和「从 mid 到末尾的论文数 n−mid」。
9. 11mid=2 → 右边 n−mid=3 篇从 mid=2 到末尾框出 3 篇(紫底窗口)。问题变成：这 3 篇能不能各自都 ≥ 3 次？由升序，只要最矮的那篇 citations[mid]=3 过关，全员就都过关。
10. 12citations[2]=3 ≥ n−mid=3 ✓citations[2]=3 ≥ n−mid=3 成立！说明右边这 3 篇确实「各自 ≥ 3 次」，h 至少能到 3。但说不定再往左还能找到更靠前的达标起点(让论文数更多)，所以要继续往左探：hi = mid−1 = 1。
11. 13记下候选，hi → 1hi 收到 1，下标 2~4 整段变灰。注意：我们没丢掉这个答案——lo 此刻还停在 0，最靠左达标起点的记录由 lo 兜着。继续在左半 [0,1] 里看能不能找到更靠前的起点。
12. 14h ≥ 3 已锁底，看左半能否更优收完 hi 别忘了：下标 2 这个达标起点(绿色 3 篇)已经入袋，候选 h=3 是保底了。接下来在左半区间 [0,1] 找的，是能不能有更靠前的起点把篇数做大。下一轮见分晓。
13. 15mid = (0+1)/2 = 0新区间 [0,1] 取中点，mid=(0+1)/2=0。再按同一条规则比一次。
14. 16mid=0 → 右边 n−mid=5 篇从 mid=0 往右就是全部 5 篇。要让 h=5，得这 5 篇每篇都 ≥ 5 次。可最矮的 citations[0]=0，差得远——这一关多半过不了。
15. 17citations[0]=0 < n−mid=5 ✗citations[0]=0 < n−mid=5 不成立。想要 5 篇各自 ≥5 次办不到。说明达标起点不可能在 mid=0 这么靠左，把 mid 及它左边全砍掉：lo = mid+1 = 1。
16. 18排除下标 0，lo → 1lo 推到 1，下标 0 变灰出局。现在 lo 和 hi 都指向 1，还满足 lo ≤ hi，再比最后一轮。
17. 19mid = (1+1)/2 = 1区间收成 [1,1]，取中点 mid=1。这是最后一搏：看看下标 1 能不能当达标起点。
18. 20mid=1 → 右边 n−mid=4 篇从 mid=1 往右框出 4 篇(引用 1、3、5、6)。要 h=4，得这 4 篇每篇都 ≥ 4 次。可最矮的 citations[1]=1 太低了。
19. 21citations[1]=1 < n−mid=4 ✗citations[1]=1 < n−mid=4 不成立。4 篇各自 ≥4 次也办不到。继续砍：lo = mid+1 = 2。这下 lo 越过 hi 了。
20. 22lo → 2，越过 hi=1lo 推到 2，下标 0、1 都变灰出局。此刻 lo=2 已经越过 hi=1，循环条件 lo ≤ hi 破了，二分该停了。lo 最终停的位置就是最靠左的达标起点。
21. 23lo=2 → h = n − lo = 5 − 2lo 最终停在下标 2——这是「能让右边整批都达标」的最靠左起点。从它到末尾共 n − lo = 5 − 2 = 3 篇(绿色高亮的 3、5、6)，每篇都 ≥ 3 次。
22. 24h = 3返回 h = n − lo = 3：有 3 篇论文各自至少被引 3 次，这就是 h 指数。5 篇论文只比了 3 轮，全程 O(log n)，没有一次多余扫描。
23. 28[1,2,100] → h=2换个例子 [1,2,100]：想要 3 篇各自 ≥3 次?citations[0]=1 不够，起点右移;下标 1 往右 2 篇(2、100)各自 ≥2 次?成立。lo 停在 1，h = 3−1 = 2。注意 100 再大也不能让 h 超过总篇数。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def hIndex(self, citations):
        n = len(citations)
        lo, hi = 0, n - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if citations[mid] >= n - mid:   # 右边这批够格 → 往左找更靠前的起点
                hi = mid - 1
            else:                           # 凑不齐 → 起点右移
                lo = mid + 1
        return n - lo

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = (int)citations.size();
        int lo = 0, hi = n - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (citations[mid] >= n - mid)   // 够格 → 往左
                hi = mid - 1;
            else
                lo = mid + 1;                // 凑不齐 → 往右
        }
        return n - lo;
    }
};

class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int lo = 0, hi = n - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (citations[mid] >= n - mid)   // 够格 → 往左
                hi = mid - 1;
            else
                lo = mid + 1;                // 凑不齐 → 往右
        }
        return n - lo;
    }
}

复杂度

面试官可能追问