同事拆迁赔了800w，还正常上班。我们都好奇他为什么不离职，结果他说:我又不怕被开，没必要像你们那么卷，找点事做也挺好的。。。

有次部门搞“算法分享午餐会”，领导兴致冲冲让我也讲一个，“最好是那种既能面试装杯、又有技术深度的题目”。我一听这要求，脑海里立刻闪过一道经典老题：计算右侧小于当前元素的个数。

这题好在哪？思维够转弯，解法够多样，暴力、树状数组、归并排序、BST、甚至Segment Tree都能派上用场，想怎么秀就怎么秀。

先讲讲题目到底是啥：

给你一个整数数组 nums，对于每个元素，计算它右边有多少个数比它小。比如输入 [5, 2, 6, 1]，输出就是 [2, 1, 1, 0]。

我刚开始接触这题的时候，还在想是不是可以一边遍历一边对右边所有元素暴力比大小，但很快就明白，这暴力解法最多也就骗骗面试官三分钟，一看时间复杂度 O(n^2)，分分钟把你踢回去优化。

后来想起归并排序可以干这个事。没错，这题可以“顺手”在归并排序过程中统计右侧比当前元素小的数，顺手赚钱，何乐而不为？

上代码👇：

classSolution {
class Pair {
int val;
int index;

        Pair(int val, int index) {
this.val = val;
this.index = index;
        }
    }

privateint[] count;

public List<Integer> countSmaller(int[] nums) {
intn= nums.length;
        count = newint[n];
        Pair[] pairs = newPair[n];

for (inti=0; i < n; i++) {
            pairs[i] = newPair(nums[i], i);
        }

        mergeSort(pairs, 0, n - 1);
        List<Integer> res = newArrayList<>();
for (int c : count) {
            res.add(c);
        }
return res;
    }

privatevoid mergeSort(Pair[] pairs, int left, int right) {
if (left >= right) return;

intmid= left + (right - left) / 2;
        mergeSort(pairs, left, mid);
        mergeSort(pairs, mid + 1, right);
        merge(pairs, left, mid, right);
    }

privatevoid merge(Pair[] pairs, int left, int mid, int right) {
        List<Pair> temp = newArrayList<>();
inti= left, j = mid + 1;
intrightCount=0;

while (i <= mid && j <= right) {
if (pairs[i].val > pairs[j].val) {
// 当前左边的元素大于右边的，说明右边这一个比它小
                rightCount++;
                temp.add(pairs[j++]);
            } else {
                count[pairs[i].index] += rightCount;
                temp.add(pairs[i++]);
            }
        }

while (i <= mid) {
            count[pairs[i].index] += rightCount;
            temp.add(pairs[i++]);
        }

while (j <= right) {
            temp.add(pairs[j++]);
        }

for (intk=0; k < temp.size(); k++) {
            pairs[left + k] = temp.get(k);
        }
    }
}

说实话，这题最妙的点是：你要在排序的同时维护原数组的位置关系，并能在拆解合并之间统计数量，这思路真的是“打游戏顺便捡材料”的典范。

而且程序员日常用到的很多“看似和排序无关的业务需求”，其实背后都离不开这种“排序+额外统计”的技巧，比如：

• • 用户排名变动统计；
• • 实时K线图中价格变动趋势；
• • 股票买入时机分析（是不是感觉能去掘金平台写点量化分析了）；

段子时间：有个哥们写这题，一开始没理解归并的那一层含义，愣是加了两个 for 循环“手动统计”右边有多少个小的，代码跑起来感觉自己像是“人肉快排”🤡。

最后我觉得这题最适合用来装杯的地方，就是：你讲归并排序统计的同时，还能顺带聊聊树状数组、平衡BST的变种写法，一顿操作猛如虎，面试官都得想想你是不是从《剑指Offer》出来的。

你说为啥这题这么重要？说白了，能看出你是不是“写代码的”，还是“懂代码的”。能写对是基本盘，能写出效率是进阶，能讲出道理是大神。

所以我现在再刷这题的时候，已经不是为了拿分，而是图一个心安：起码面试官让我做题的时候，我心里有数，而不是慌里慌张地开两个for循环碰运气。

你要是准备面试、刷题、或者纯粹喜欢给大脑做马杀鸡，这题必须得刷！而且得吃透。

至于要不要跟领导汇报我这题讲得多好，我一般只说一句话：“代码写完了，战绩看控制台输出”。