企业官网建设流程全解析

1. 先把题意拆开：这不是单纯的排序题

看到“计算右侧小于当前元素的个数”这个标题，我第一反应是又遇到一道“披着排序外衣的统计题”。题目本身不复杂：给你一个数组nums，对每个位置i，统计所有满足j > i并且nums[j] < nums[i]的元素个数。比如[5,2,6,1]的结果是[2,1,1,0]：5 右侧比 5 小的是 2 和 1，所以是 2；2 右侧比 2 小的是 1；6 右侧比 6 小的是 1；1 右侧没有更小元素。

最直白的做法是两层循环，外层固定i，内层从i+1扫到末尾。数据量小的时候完全没问题，但一旦n到10^5这个量级，O(n^2)就明显扛不住了。我最早刷这道题时就是先写暴力的，结果被超时教育了一通。暴力的瓶颈在于：每统计一个i，都要重新扫描右侧段，完全没有把已经有的大小关系复用起来。这道题真正考的，是怎么在一次排序过程中，顺便把“每个元素右侧有多少个比它小”这件事算完。

这里要理解一个关键点：它和“逆序对总数”不一样。逆序对的定义是i < j且nums[i] > nums[j]，我们只需要统计有多少对这样的(i, j)。而本题要的是“每个i作为逆序对中左边那一个元素时，它自己贡献了多少对”。也就是说，逆序对总数是所有i的答案之和，但题目要求把总数拆回到每个i头上。这个拆分的需求，决定了我们不能只维护一个全局计数器，而是要对每个原下标单独累加。

如果你只是会写“求逆序对总数”的归并排序，那很容易在这道题上翻车，因为计数位置和累加方式都变了。后面我会专门讲这个差异。

2. 归并排序为什么能顺手解决这道题

2.1 每个“右小元素”关系都只会被处理一次

分治解法的核心在于归并排序的递归结构。假设当前正在处理数组区间[l, r)，把它分成左半[l, mid)和右半[mid, r)。对任意一对满足i < j的下标，它们要么同时落在左半，要么同时落在右半，要么一个在左半、一个在右半。前两种情况会在更深的递归层被继续处理，后一种情况则正是在当前这一层合并时被统计。

也就是说，任何一个“右侧小于当前元素”的计数关系，都会在某个归并层被恰好处理一次：当且仅当发生计数的那两个元素在当前区间的左右两侧。这是归并排序能解决这类问题的天然前提。左右两侧各自排序完成后，左半和右半内部的有序性已经不重要了，重要的是两个子数组在合并时依然保持着原始数组的相对顺序：左半的所有元素在原始顺序上都位于右半所有元素之前。

2.2 合并时，右侧元素比左侧元素先“出队”就是答案

合并两个有序数组的标准操作，是用两个指针i和j分别指向左半和右半，每次把较小的那个放进临时数组。这里我们需要稍微修改一下计数逻辑。

当nums[i] <= nums[j]时，我们把左半当前元素放进临时数组。这时候，右半指针j已经移到了某个位置，j - mid就是右半中已经被放进临时数组的元素个数。由于右半是有序的，而且内部元素是按照“当前右半元素小于左半当前元素”这一条件逐个放出来的，所以这j - mid个元素全部是严格小于当前左半元素的值。它们又都来自右半，也就是在当前元素原始位置的右侧。于是答案就清清楚楚了：

当左半元素nums[i]被放入临时数组时，ans[当前元素的原始下标] += j - mid。

反过来，如果nums[i] > nums[j]，说明右半当前元素更小，我们直接把它放到临时数组里，不需要对任何答案数组累加。因为它本身是右半元素，它的“右侧更小元素”要在递归中或者更靠右的子数组中去统计，而不是在当前这一层由左半来贡献。

这里有个细节：合并操作最终会把当前区间排成有序，但这并不影响原始下标。我们只需要在递归过程中始终记录每个元素原本属于哪个位置，就能把统计结果准确写回到ans的对应位置上。

2.3 相等元素必须“左先出”，否则会把等于也算成小于

这个点特别容易踩。比较条件要用<=，也就是左半元素小于等于右半元素时，优先移动左半指针。为什么要这样？因为题目要求的是“严格小于”，而右半指针j - mid统计的是“已经被拿出来的右半元素个数”。如果两个值相等，而你在合并时先把右半那个相等的元素拿出来，等左半元素再出队时，就会把这个相等的元素也算进“更小元素”里，答案就变大了。

最简单的验证是[5,5,5]，正确答案是[0,0,0]。如果合并时采用if (left < right)才取左半元素，那么在第一次合并时，右半的 5 会先被取走，等左半的 5 再被取走时，j - mid已经等于 1，于是会错误地统计出 1 个“更小元素”。我的建议是先把这一条写在代码旁边：“相等时取左边，是为了保证不把相等元素计入严格更小。”

3. 可复现的实现：带原下标的归并排序

3.1 数据结构设计

因为归并排序会不断改变元素在数组中的位置，我们不能只存数值，否则排序结束后不知道这个值原本对应哪个位置。我习惯用一个pair<int, int>来存储，first存数值，second存原始下标。

class Solution { public: vector<int> countSmaller(vector<int>& nums) { int n = nums.size(); vector<pair<int, int>> a(n), tmp(n); for (int i = 0; i < n; ++i) { a[i] = {nums[i], i}; } vector<int> ans(n, 0); auto mergeSort = [&](auto&& self, int l, int r) -> void { if (r - l <= 1) return; int mid = l + (r - l) / 2; self(self, l, mid); self(self, mid, r); int i = l; int j = mid; int k = l; while (i < mid && j < r) { if (a[i].first <= a[j].first) { ans[a[i].second] += j - mid; tmp[k++] = a[i++]; } else { tmp[k++] = a[j++]; } } while (i < mid) { ans[a[i].second] += j - mid; tmp[k++] = a[i++]; } while (j < r) { tmp[k++] = a[j++]; } for (int p = l; p < r; ++p) { a[p] = tmp[p]; } }; mergeSort(mergeSort, 0, n); return ans; } };

这段代码是典型的半开区间写法：[l, r)表示当前要处理的区间，左半是[l, mid)，右半是[mid, r)。递归的终止条件是区间内元素数量小于等于 1，这时候不需要排序也不需要统计。

3.2 两个while循环不能少

第一次while循环结束后，只会有两种情况：要么左半元素已经全部处理完，要么右半元素已经全部处理完。

如果是右半全部处理完，而左半还剩下一部分元素，那说明这些剩余左半元素是当前区间里最大的那部分，右半的每一个元素都已经在它们之前被放进临时数组。因此当它们一个一个出队时，都需要把右半的全部元素数量r - mid加到它们的答案里。这正是第二个while循环做的事情：

while (i < mid) { ans[a[i].second] += j - mid; tmp[k++] = a[i++]; }

有些版本会把这段写成固定的+= r - mid，逻辑上也是一样的，因为此时j == r。但为了和前面的j - mid保持一致性，我更喜欢直接写j - mid，一眼就能看出“右半已经出队的数量”。

第三个while只是把剩下的右半元素搬运进临时数组，这部分不再产生统计。最后把临时数组拷贝回a，当前区间就排好序了。

3.3 时间与空间复杂度

每一层归并都是对整个区间的一次线性扫描，递归深度是O(log n)，所以时间复杂度是O(n log n)。空间上需要一个和原数组等大的临时数组，以及一个答案数组，总共O(n)。递归栈深度是O(log n)，对n = 10^5来说完全不是问题。

对比暴力解法的O(n^2)，归并排序版本的好处不仅在于复杂度降低，更在于它没有引入值域相关的约束。元素是负数、浮点数（在部分语言场景下）、还是大到10^9，都不需要额外处理，因为排序只依赖元素之间的相对大小。

4. 避坑笔记与调试技巧

4.1 相等元素处理不当

这是第一大坑。前面已经提过，条件必须写<=，保证左半元素优先出队。为了加深印象，我用一个小例子说明错误的样子：

[3,1,3]这个例子尤其容易错：下标 0 的 3 右侧只有 1 比它小，下标 2 的 3 右侧没有元素。如果合并时把相等的右半 3 先取出，下标 2 的 3 就会在下标 0 的 3 之前进入临时数组，导致下标 0 的 3 统计出两个“更小元素”，正确答案的 1 就变成 2 了。

4.2 用错下标：排序后的位置不是原位置

另一个常见问题是在合并时写成了ans[i] += j - mid，或者用ans[k]来累加。这里的k是临时数组的写入位置，它只是“排序后当前元素应该去的位置”，和“这个元素在原始数组里的下标”完全是两回事。

比如[5,2,6,1]，合并完左半[5,2]后，a里第二个位置放的是 5 吗？不是，是(2,1)和(5,0)。如果此时你用当前数组位置当作答案下标，那统计的是 2 的个数还是 5 的个数，完全取决于排序后的顺序，结果必然错乱。所以务必在开始时就把原始下标存下来，所有累加都用a[i].second。

4.3 别把“求逆序对总数”的代码直接搬过来

求逆序对总数的归并排序，计数是在取出右半元素时进行的：每取出一个右半元素，说明左半还剩mid - i个元素都比它大，于是把这mid - i加到一个全局变量上。

本题则是每取出一个左半元素时，把右半已经取出的数量j - mid加到这个左半元素对应的ans上。这两者的“时机”和“累加目标”完全不同：

我第一次写的时候就是从“求逆序对总数”的模板改的，只改了累加位置，却忘了把计数时机从右半元素移动到左半元素来，结果[5,2,6,1]跑出来乱七八糟。这个差异值得你单独记一下。

4.4 用表驱动调试

依赖打印日志在递归代码里比较吃力，我更喜欢直接在小规模用例上验证，配合手写推导。下面几个用例对排查问题很有用：

调试时还可以只输出每次合并前的左半、右半以及mid，再手工核一遍某几个元素的ans，会比盯整个递归过程轻松很多。

5. 从这题往外走一步

5.1 树状数组和线段树怎么做

如果面试允许换思路，这道题最常见的替代方案是从右往左扫描，配合树状数组。具体做法是：对值域做离散化，然后倒序遍历原数组。每遇到一个nums[i]，先查询树状数组中小于nums[i]的元素个数，再把这个值插入树状数组。因为扫描是从右往左的，所以查询到的所有元素都天然位于i的右侧，一次查询就是答案。

树状数组写起来可能更短，但它有一个前提：值域必须能映射到1..k的连续整数，并且你要么提前排序去重，要么用动态开点的方式处理。而归并排序的分治版本完全不需要离散化。如果nums里出现超大整数、负数，甚至结构体对象，只要它们之间能比较大小，分治版本就能跑。

5.2 什么时候优先选分治版本

我个人更推荐先掌握归并排序版本，理由有三个。

第一，它不依赖值域，省去离散化这一步，逻辑的“主战场”只在合并排序本身。第二，它直接体现了“每个计数关系归属于哪个左元素”的本质，对理解逆序对问题有很大帮助。第三，归并排序可以很方便地扩展到类似问题，比如“右侧大于当前元素的个数”只需要把比较方向倒过来；“左侧小于当前元素的个数”可以换一种扫描方式或者调整左右半的统计规则。树状数组更适合在线场景，比如边插入数据边查询，或者需要动态修改数值的题目。但就这道题而言，分治解法和树状数组解法的时间复杂度同为O(n log n)，没有本质差距。

5.3 我的实操经验

我自己的习惯是：遇到这种“右小计数”题，先写一个归并排序分治版本跑通，再去写树状数组版本对照。写完分治版本后，你会对“元素出队顺序”和“左右半已处理数量”非常敏感，这时再看树状数组，就会觉得它只是把统计的载体从合并过程换成了线段树/树状数组而已。

另外一个小建议：写归并排序时，区间定义一定要从头到尾保持一致。我用的半开区间[l, r)其实就是 C++ STL 里begin和end的习惯，递归左右子区间分别是[l, mid)和[mid, r)，可以避免很多+1/-1的边界错误。如果你也准备用类似写法，建议把这段核心逻辑默写下来，先用小样例验证一遍，再提交到在线评测系统。这种分治统计题的出错点非常集中，只要避开了“相等元素”和“原下标丢失”这两个坑，基本就能一次写对。