H 指数 II

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

这是全题的命根子。站在下标 mid 上往右看：右边(含自己)有 n−mid 篇，它们的引用全都 ≥ citations[mid](升序保证)。于是只要 citations[mid] ≥ n−mid，这 n−mid 篇就同时满足「各自 ≥ (n−mid) 次」——h 至少能到 n−mid。

我们其实在找最靠左的那个达标起点：从它到末尾的论文数就是 h。盯住下面 lo/hi/mid 三根指针，看 citations[mid] 和 n−mid 一比，区间怎么一刀刀收缩。最后答案 = n − lo。

理解 n−mid · 站在下标 2 往右看：先把「n−mid」这个量看明白。站在下标 2 上，紫底窗口框住的就是它到末尾的 3 篇(引用 3、5、6)。因为升序，这 3 篇每一篇都 ≥ citations[2]=3。

理解 n−mid · 站在下标 3 往右看：再往右挪到下标 3：窗口缩成2 篇(引用 5、6)。下标越往右，n−mid 越小，但门槛 citations[mid] 越高——这一升一降之间，存在一个最佳平衡点，二分要找的就是它。

理解 n−mid · 站在下标 0 往右看：退到最左下标 0：窗口张到全部 5 篇，可门槛塌到 0——想让 5 篇都 ≥5 次根本办不到。起点太靠左，篇数虽多却没人达标。二分要在「篇数」和「门槛」之间挑出最甜的那个点。

开局 · 二分范围：正式开二分。lo 指数组头(下标 0)、hi 指数组尾(下标 4)。我们要在 [lo,hi] 里夹出那个最靠左的达标起点，循环用 lo ≤ hi，结束时答案 = n − lo。

第1轮 · 取 mid：取中点 mid=(0+4)/2=2。接下来要比的是 citations[mid] 和「从 mid 到末尾的论文数 n−mid」。

第1轮 · 看右边这批：从 mid=2 到末尾框出 3 篇(紫底窗口)。问题变成：这 3 篇能不能各自都 ≥ 3 次？由升序，只要最矮的那篇 citations[mid]=3 过关，全员就都过关。

第1轮 · 比 citations[mid] 与 n−mid：citations[2]=3 ≥ n−mid=3 成立！说明右边这 3 篇确实「各自 ≥ 3 次」，h 至少能到 3。但说不定再往左还能找到更靠前的达标起点(让论文数更多)，所以要继续往左探：hi = mid−1 = 1。

第1轮 · 收 hi=mid−1：hi 收到 1，下标 2~4 整段变灰。注意：我们没丢掉这个答案——lo 此刻还停在 0，最靠左达标起点的记录由 lo 兜着。继续在左半 [0,1] 里看能不能找到更靠前的起点。

第1轮 · 当前最佳候选：收完 hi 别忘了：下标 2 这个达标起点(绿色 3 篇)已经入袋，候选 h=3 是保底了。接下来在左半区间 [0,1] 找的，是能不能有更靠前的起点把篇数做大。下一轮见分晓。

第2轮 · 取 mid：新区间 [0,1] 取中点，mid=(0+1)/2=0。再按同一条规则比一次。

第2轮 · 看右边这批：从 mid=0 往右就是全部 5 篇。要让 h=5，得这 5 篇每篇都 ≥ 5 次。可最矮的 citations[0]=0，差得远——这一关多半过不了。

第2轮 · 比 citations[mid] 与 n−mid：citations[0]=0 < n−mid=5 不成立。想要 5 篇各自 ≥5 次办不到。说明达标起点不可能在 mid=0 这么靠左，把 mid 及它左边全砍掉：lo = mid+1 = 1。

第2轮 · 推 lo=mid+1：lo 推到 1，下标 0 变灰出局。现在 lo 和 hi 都指向 1，还满足 lo ≤ hi，再比最后一轮。

第3轮 · 取 mid：区间收成 [1,1]，取中点 mid=1。这是最后一搏：看看下标 1 能不能当达标起点。

第3轮 · 看右边这批：从 mid=1 往右框出 4 篇(引用 1、3、5、6)。要 h=4，得这 4 篇每篇都 ≥ 4 次。可最矮的 citations[1]=1 太低了。

第3轮 · 比 citations[mid] 与 n−mid：citations[1]=1 < n−mid=4 不成立。4 篇各自 ≥4 次也办不到。继续砍：lo = mid+1 = 2。这下 lo 越过 hi 了。

第3轮 · 推 lo=mid+1：lo 推到 2，下标 0、1 都变灰出局。此刻 lo=2 已经越过 hi=1，循环条件 lo ≤ hi 破了，二分该停了。lo 最终停的位置就是最靠左的达标起点。

二分结束 · 算答案：lo 最终停在下标 2——这是「能让右边整批都达标」的最靠左起点。从它到末尾共 n − lo = 5 − 2 = 3 篇(绿色高亮的 3、5、6)，每篇都 ≥ 3 次。

取出答案：返回 h = n − lo = 3：有 3 篇论文各自至少被引 3 次，这就是 h 指数。5 篇论文只比了 3 轮，全程 O(log n)，没有一次多余扫描。

雷区实演 · 全员高引用：换个例子 [1,2,100]：想要 3 篇各自 ≥3 次?citations[0]=1 不够，起点右移;下标 1 往右 2 篇(2、100)各自 ≥2 次?成立。lo 停在 1，h = 3−1 = 2。注意 100 再大也不能让 h 超过总篇数。

边界三连：三种极端：全 0、单篇高引、单篇 0 引。循环 lo≤hi 配上「n−lo」的收尾，把它们都兜得稳稳的。

面试追问：把「有序才能二分」「citations[mid]≥n−mid 的含义」「lo 为何是答案」讲透，是这题的面试加分项。