阿里编程题4星刷题体验：从算法建模到树状数组的实战解析

阿里编程题刷到4星是什么体验？我的感受是：它不是难，是巧。难是你看不懂答案，巧是你看懂答案之后会想抽自己——原来绕了这么大一圈，核心思路就那几步。很多人在阿里云开发者社区里看到“【2023】阿里巴巴编程题（4星）”这个标签时，下意识会觉得这是给竞赛选手准备的，跟普通开发者没什么关系。实际刷下来，我的判断是：4星题刚好卡在一个很有意思的位置，它不需要你掌握冷门高级算法，但需要你把常见的数据结构和经典模型用到真正熟练，还要能扛住边界条件和复杂度的双重考验。

如果你刚把LeetCode简单题刷完、或者正在准备大厂笔试，那么这个星级的题目非常值得作为下一阶段的训练目标。本文我会从4星题在阿里题目体系中的真实定位说起，分析它最常出现的题型方向，再用一道典型题目完整走一遍从读题到提交通过的链路，最后聊一聊我刷这类题踩过的坑和总结出的训练顺序。

1. 4星题在阿里编程题体系中的真实定位

阿里编程题是阿里云开发者社区算法题库里的一个常驻系列，按难度从1星到5星划分，4星处于“中等偏上”那一档。很多人在社区刷题时会顺便看到阿里云开源镜像、服务器部署之类的运维话题，其实这些和编程题属于不同板块，只是社区放在了一起，容易让人误以为刷题要配合云服务器环境。实际上这个在线题库直接在浏览器里就能写，和服务器的IP地址、镜像站没有任何关系。

1.1 “4星”难的不是算法，而是建模

1星到2星的题目基本是“模板题”，看到题目就能想到对应套路，比如冒泡排序、链表反转、基础递归，写出来就能过。3星开始有一点组合味道，需要把两个基础技巧拼起来。到了4星，情况会明显变化：题目描述里经常看不到任何算法关键词，场景包装也更加自然，比如“电商大促时优惠券叠加怎么算最优”“物流配送路径怎么选”“用户行为序列里怎么找异常模式”。你看着像业务题，实际内核是动态规划、贪心、图论或者数据结构优化。

我举个直白例子。如果把算法题比作盖房子：1星题是给你图纸让你砌墙，2星题是让你自己画个简单图纸再砌墙，3星题是材料已经备好但需要你自己选哪些能用，4星题则是只告诉你“我要一个能住人的房子”，你得自己判断该用砖还是用钢结构、要做几层、门窗怎么开。题目并不要求你发明新建筑材料，用到的东西都是课本里出现过的，难的是怎么在模糊条件下把这个“建模”做对。

1.2 4星题对标的是正式笔试的什么水平

参加过互联网公司笔试的人应该有体感：笔试题目通常不是一道巨型难题，而是几道难度梯度不同的题混在一起。4星题的强度大约对应大厂笔试题中用来区分“进入下一轮”和“止步于此”的那道核心题，也是面试手撕代码环节里“附加题”的常见难度。

2019年到2021年那阵子，字节、阿里、腾讯的线上笔试题都明显提升了场景包装复杂度，题干可能长达半页纸，但去掉干扰信息后核心考点就是4星题级别的东西。所以刷透4星题，不只是为了在刷题平台拿个成就，而是直接服务于真实笔试场景。

我刷完几十道4星题之后的直观体会是：如果4星题能稳定在60分钟内做出并提交通过，那大多数大厂笔试里的算法题都不会构成太大威胁。不用追求5星题那种偏竞赛向的难度，4星已经足够覆盖绝大多数在职开发者的笔试需求。

2. 4星题最常出没的五个题型方向

光说“4星题难在建模”还不够，得知道它具体在哪些方向出没。我翻了上百道阿里系4星题以及同类平台的中高难度题，发现高频方向其实非常集中。

2.1 动态规划：最难的不是状态转移，而是状态怎么问

4星题里的动态规划很少直接说“用DP”，更像是一种“求满足条件的方案总数”或者“最小化某种代价”的描述。难点在于你需要自己识别出这是一个多阶段决策问题，然后把每一阶段的“状态”定义清楚。很多人在这一步卡住，不是不会写转移方程，而是压根没往DP方向想。

识别动态规划有一个很实用的信号：题目中有“按顺序”的隐藏语义。比如处理数组时只能从左往右扫描、安排任务时有先后依赖、切割序列时每一段的状态由前面所有段的状态决定——这些词的背后往往就是动态规划。另一个信号是数据范围，n到10^3级别可能就是O(n^2)的DP，n到10^5级别大概率需要优化到O(nlogn)甚至O(n)。如果观察到了这两个信号，基本可以先把暴力搜索从大脑里划掉，拿DP的思路去套。

2.2 贪心与构造：没有模板，只有“为什么这样贪是对的”

贪心题看起来代码量很少，有时候核心循环就十几行，但难的是如何证明局部最优能推出全局最优。4星题里经常出现的贪心场景是任务调度、区间覆盖和资源分配，这些场景业务上也特别常见，比如直播转码资源分配、分布式任务调度、广告库存分配。

很多人在一道贪心题上卡了两小时，最后发现答案其实就是排序加一个优先队列，代码贼短，于是非常懊恼。我现在的建议是，面对贪心题别急着写代码，先在草稿纸上做小规模例子推导，看每一步选择“当前看起来最好的”是否会让整体变差。如果推导了三五个例子都没有反例，那么贪心正确性的概率就很高。这个“证明前置”的习惯比代码能力值钱得多，也是4星题和低星题最大的区别。

2.3 图论：边权怎么拆，比算法本身更重要

4星题里的图论题很少直接给你一张干净的图，更多是让你自己把关系抽象成图。比如给一批任务和依赖关系，问最少需要多少轮才能执行完，这就是拓扑排序的典型应用；给一批城市和道路，问在某个时间约束下能否从A城到B城，这可能是最短路的变体。

我做这类题最大的体会是：大部分时候难点不在Dijkstra或BFS模板本身，而在于怎么把题目条件转换成“边”和“边权”。有段时间我遇到图论题就头大，后来想通了一件事：图的建模就是“对象是节点，关系是边，代价/收益是边权”。一旦把关系理清楚，后面套算法几乎是不需要思考的。

2.4 字符串与哈希：把暴力优化到能跑的过程记录

4星题中字符串题的高频考点是子串统计、模式匹配、循环节判断和回文相关。暴力做法大多简单，但n一大就超时。这类题考察的是如何用哈希把字符串比较的复杂度从O(L)降为O(1)，或者用滑动窗口把枚举的复杂度降一个维度。

字符串哈希的原理其实不复杂：把字符串看成一个高进制数，配合前缀哈希数组，就能在常数时间内算出任意子串的哈希值。但具体实现时有一个坑，那就是模数选择不好会造成哈希冲突，这点在后面的踩坑部分我会详细展开。

2.5 思维与数学题：4星题里那个最像“脑筋急转弯”的方向

还有一种常见类型是数学推导和计数问题。这类题的特征是代码写起来可能更短，但推理过程较长。比如给出一个排列，问满足某种大小关系的三元组有多少个，这类问题经常会用到枚举中间元素加树状数组实时维护统计信息。它表面是数学题，内核是数据结构优化，非常典型的4星题风格。

3. 从读题到提交通过：一道4星题的完整解题链路

这一节我挑一道很有代表性的计数题，完整走一遍解题链路。先说清楚，我拿的这个题目并不是阿里平台上的原题，但它的风格、难度和解法路径和4星题很一致，适合用来展示解题方法。题目大意如下：

给定一个长度为n的整数数组a，求满足 i < j < k 且 a[i] < a[k] < a[j] 的三元组 (i, j, k) 的数量。数据范围：n ≤ 10^5，a[i] ≤ 10^9。模数不要管，结果在64位整数范围内。

这种题就是典型的“描述简单，解法不简单”的类型。第一眼看上去暴力三重循环就能做，但 n 到 10^5 后暴力是 O(n^3)，显然不可能通过。

3.1 读题阶段最容易踩的“语义陷阱”

第一次看到这个题，我脑子里的第一反应是：这不就是求一个“凸”形状的三元组吗？中间j位置的数要最大，右侧k位置的数要居中，左侧i位置的数要最小。逻辑上是在数组里找“高—低—中”的结构。

如果直接枚举i和j，再找右侧落在两个区间之间的k，复杂度是O(n^2)级别的查询。就算用二分，也要先对右侧排序，可一旦排序就破坏了k必须在j右侧这个位置约束。这里最容易犯的错误，就是把“值的大小关系”和“位置的先后关系”搞混。4星题读题阶段最大的坑不是生词，而是这种藏在句子里的位置约束。

我的读题习惯是：先圈出所有下标关系词和数值关系词，在草稿纸上用一行示例数组手推一遍，把“a[i] < a[k] < a[j]”这种条件翻译成“j是最大值的锚点，k值夹在i和j之间”。这一步做扎实，后面建模才不会歪。

3.2 核心建模：枚举中间元素，把三元组拆成两段统计

暴力解法不行，就要降低复杂度。观察约束条件，j 夹在 i 和 k 中间，且 a[j] 是三者里最大的。这个“锚点”性质非常关键，因为只要枚举 j，剩下的问题就变成：在 j 左侧找 a[i] < x，在 j 右侧找 a[k] = y，并且要求 x < y < a[j] 的数对数量。

如果直接枚举j，再枚举左侧和右侧，复杂度还是O(n^2)。但注意，左侧的条件是“值小于某个阈值”，右侧的条件也是“值落在某个区间”，这种问题天然适合用值域上的数据结构来维护。

思路可以这样转换：从右往左扫描数组。当扫描到位置k时，把它当作三元组里的k，那么需要统计的是它左边存在的“以某个j为锚点、且a[i]小于当前a[k]的(i,j)对数量”。这里的难点是不仅要维护左侧节点，还要同时维护“值的两两关系”。

绕了一段时间后，我找到了一种解法：用两个树状数组。第一个树状数组bit_cnt维护每个数值作为a[i]在左侧出现的次数；第二个树状数组bit_pair维护“以某个值为a[j]、且已经找到了合适的a[i]”的数对数量。从右往左扫描时，每遇到一个新的a[k]，答案累加bit_pair中值小于a[k]的所有数对数量乘以... 等等，这中间还需要处理j必须在k左侧的问题。

再理一遍：我的最终方案是从左往右枚举j，同时维护j左侧所有a[i]的计数，然后需要在j右侧找到所有满足 a[k] 在 (a[i], a[j]) 之间的k。这个“右侧所有k”的信息也需要预处理。一个可行的套路是：先从右往左扫描一遍，用树状数组记录每个位置右侧有哪些值出现（用后缀计数表示）。然后枚举j时，左侧用另一棵树状数组记录a[i]的计数，右侧用预处理的计数数组查询区间和。这样对每个j，查询左侧树状数组中小于a[j]的i个数，再对应右侧区间和做乘积？不对，那样就把i和k的配对数量直接相乘了，实际上左侧每个i和右侧每个k只要满足 a[i] < a[k] < a[j] 就都能配对，所以确实可以枚举j，然后对每个j：

• leftCount = 左侧所有小于a[j]的a[i]数量
• rightSum = 右侧所有值落在区间(某个a[i], a[j])内的a[k]的数量

这个“某个a[i]”对每个i不一样，不能直接用一个全局区间。结果这种方法走不通。

正确的做法应该反过来：枚举k，用树状数组维护所有可能成为(i,j)组合的数量。具体来说，从左往右扫描，在扫描到位置k时，我们想知道在k左边有多少个“i和j”满足 a[i] < a[k] < a[j]。此时把每个j看作一个“开放的中间锚点”，它对应的可行i的个数可以统计。当遇到新的a[k]时，答案累加所有“锚点值a[j] > a[k]”的已统计i对数量。

如果用树状数组维护“每个候选j值，左侧已经有多少个小于它的i”，那么新来的a[k]对答案的贡献就是所有候选j值大于a[k]的“已统计i数量”之和，也就是树状数组的后缀和。实现上先离散化，然后：

1. 从左往右扫描数组下标t。
2. 在扫描到t时，先把a[t]加入“左侧出现次数”的计数中，这对应它将来可以作为i。
3. 然后计算当前以a[t]为j时，左侧所有小于a[t]的i个数，并把这个值更新到另一个树状数组“候选j值”位置a[t]上。
4. 如果t作为k，那么它产生的答案贡献就是在“候选j值”树状数组中查询所有值大于a[t]的count之和。

这个顺序有点绕，但画个图就很清晰。核心就是用一棵树状数组维护“每个值作为j时有多少个合法的i”，另一棵维护“每个值作为i的出现次数”。当扫描到每个位置时：

• 先查询树状数组B中大于当前值v的“j对数量”总和，加入答案。
• 然后查询树状数组A中小于v的i个数，把这个数量加到B的v位置上（代表以当前值为j，左侧可配对的i数）。
• 最后把v在A中的计数加1，使它成为后续位置的i候选。

这个流程从左往右一遍扫完，复杂度是O(n log n)。对了，别忘了数据范围是10^5，要先用排序做离散化，把值域压缩到n以内。

3.3 代码实现：两个树状数组的细节与验证

下面是我用C++实现的版本，思路就是上面分析的“一个树状数组存i出现次数，一个存j对数量”。

#include <bits/stdc++.h> using namespace std; typedef long long ll; struct BIT { int n; vector<ll> c; BIT(int n) : n(n), c(n + 1, 0) {} void add(int idx, ll val) { for (; idx <= n; idx += idx & -idx) c[idx] += val; } ll sum(int idx) { ll res = 0; for (; idx > 0; idx -= idx & -idx) res += c[idx]; return res; } // 查询 (l, r] 区间的和，l和r都是离散化后的下标 ll rangeSum(int l, int r) { if (l > r) return 0; return sum(r) - sum(l); } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<ll> a(n); vector<ll> vals; for (int i = 0; i < n; i++) { cin >> a[i]; vals.push_back(a[i]); } // 离散化 sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); auto getId = [&](ll x) { return int(lower_bound(vals.begin(), vals.end(), x) - vals.begin()) + 1; }; vector<int> b(n); for (int i = 0; i < n; i++) b[i] = getId(a[i]); int m = vals.size(); BIT bitI(m), bitJ(m); // bitI: i出现次数, bitJ: 每个值作为j的合法i对数 ll ans = 0; for (int t = 0; t < n; t++) { int v = b[t]; // 1. 当前t作为k：累加所有值大于a[t]的j对数量 ans += bitJ.rangeSum(v, m); // 2. 当前t作为j：查询左侧小于a[t]的i个数，作为j对数量更新到bitJ ll leftLess = bitI.sum(v - 1); bitJ.add(v, leftLess); // 3. 当前t作为i：加入bitI bitI.add(v, 1); } cout << ans << '\n'; return 0; }

这个代码我提交过类似的题目，几个关键点需要留意。第一，离散化后的下标从1开始，树状数组要用1-based，不然后面区间查询会乱。第二，ans必须用long long，三元组数量在n=10^5时最坏情况下是 C(10^5, 3) 级别，也就是大约1.67×10^14，远超int范围。第三，扫描顺序很重要：在位置t上先把它当作k来结算答案，再把它当作j更新数据，最后把它当作i加入左侧集合，顺序错了结果就会不对。

3.4 用暴力对拍验证思路

很多人在OJ上提交一遍不过就慌了，我今天特别想说一下“对拍”这个技巧，它才是刷4星题效率最高的利器。写完高效解之后，不要直接交，先写一个O(n^3)的暴力版本，用随机小数据跑几百组，两个程序结果一致再提交。

这段暴力代码就是三重循环，n不超过100时随便跑：

ll brute(vector<int>& a) { int n = a.size(); ll res = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int k = j + 1; k < n; k++) { if (a[i] < a[k] && a[k] < a[j]) res++; } } } return res; }

对拍思路是：写一个gen.py生成随机数组，反复喂给暴力程序和高效程序，比较输出。我第一次跑对拍时，高效程序在几个边界case下就漏算了，原因是离散化后bitJ.rangeSum(v, m)把等于v的情况也算进去了，但题目要求a[k] < a[j]，也就是严格小于。改成rangeSum(v + 1, m)之后才通过。这个坑在4星题里非常典型，差一个等号，答案就差一大截。

4. 我在刷4星题中踩过的坑：三条真实排查记录

刷4星题的过程里，我记录了不少自己做错的题目，翻看复盘笔记，发现错误基本集中在三个类型。它们单独拎出来都不难，但组合在一起就很磨人。

4.1 第一坑：输入输出格式没读全，多组数据直接白给

有些4星题不会明说“多组数据”，而是写一句“输入包含多组测试数据，以EOF结束”。很多刷题人习惯写单组数据读完n就处理，结果在OJ上只过了一个样例，剩下的全超时或者答案错误。

处理EOF输入的正确姿势是：

int n; while (cin >> n) { vector<ll> a(n); for (int i = 0; i < n; i++) cin >> a[i]; // 处理一组 cout << solve(a) << '\n'; }

如果用Python，则是：

import sys def solve(a): pass data = list(map(int, sys.stdin.read().split())) idx = 0 while idx < len(data): n = data[idx] idx += 1 a = data[idx:idx+n] idx += n print(solve(a))

这种一次性读取再按块分割的方式，比逐行处理更快也更不容易出错。我在多组数据题目上吃过两次亏后，现在读题阶段就会主动寻找“多组”“EOF”“直到文件结束”这些关键词。

4.2 第二坑：树状数组/线段树数组开小，运行期才崩溃

树状数组类题目的代码结构相似，最隐蔽的问题是初始化大小。如果离散化之后的唯一值个数为m，那么树状数组大小必须是m + 1（因为下标从1开始）。很多人在原数组长度n上开树状数组，一旦输入数据包含重复值，实际离散化后的m小于n，倒也不一定崩；但反过来，如果值是负数且没有做离散化就直接作为下标使用，那基本是必崩或者答案错误。

我的习惯是凡是遇到值域大、需要按值操作的数据结构题，第一步就做离散化，并且把树状数组大小统一写成m + 1，绝不直接用n。这个习惯让我少踩了很多编译器都不会报错、只在运行期诡异出错的问题。

另外，树状数组的add操作里，idx的步进用的是idx += idx & -idx。如果idx为0会导致死循环，所以所有下标必须保证从1开始。这也是一个很容易被忽略的细节。

4.3 第三坑：时间复杂度算对了，常数太大还是会超时

有时候你知道正确解法是O(n log n)，代码也写对了，但提交后就是TLE。这种情况在Java和Python中更常见，C++也会因为使用memset清零大数组而拖慢。我的排查顺序是：

1. 把输入输出缓冲关闭，C++里就是加那两行 ios::sync_with_stdio(false) 和 cin.tie(nullptr)。这一行能解决一半的TLE。
2. 看是否有多余的排序，比如在循环里反复sort，这一步每次O(n log n)叠加起来非常致命。
3. 检查是否能用int的地方用了long long。64位运算在部分评测机上比32位慢不少，但计数题非用不可时不要省。
4. 如果用了vector，尝试预分配空间 reserve，避免频繁扩容拷贝。

有一次我在一个4星题上卡了很久，最后发现是循环里调用了常数很大的unordered_map，换成数组计数后直接快了十倍。对性能敏感的题目，能用数组就别用哈希表，能用静态数组就别用vector动态扩容。

5. 刷完近百道4星题后，我总结出的训练顺序

最后这部分分享一下我的训练安排。如果你瞄准的是“把4星题刷明白”而不是“做几道体验一下”，那一个合理的训练顺序会很有用。

5.1 阶段一：先把2星3星当热身，不要急着跳级

我见过不少朋友一上来就去挑战4星题，结果每题都卡两小时，挫败感极强，刷三天就放弃了。我的建议是，先感受一下3星题的“组合感”，确保排序、二分、栈、队列、基础DP这些常用工具在30分钟内能写出来。3星题不需要大量刷，100道左右足够建立手感。

这个阶段的验收标准是：看到题能快速说出数据结构和复杂度，而不是能背出答案。

5.2 阶段二：按专题刷4星，一次吃透一个方向

我自己的顺序是：动态规划 → 贪心与构造 → 图论 → 字符串与哈希 → 思维与计数。每个专题刷15到20道，期间不做新题，只复盘旧题。专题刷法的好处是能让大脑对同一类模型形成条件反射，比如看到“子序列+最值”就自动开始想DP状态，看到“区间+统计”就自动往树状数组和线段树上靠。

刷题时做好分类笔记，记录每道题的模型关键词。比如“第12题：区间最大覆盖，贪心+优先队列”，这样一个月后复习时，你不需要重新读完整题目，只看关键词就能快速回忆起来。

5.3 阶段三：限时模拟，直接对标笔试现场

当4星题专项刷到一定量后，我开始模拟笔试环境：随机挑4道题，120分钟，不管做不做得完，时间到就停。这个阶段最重要的不是题量，而是练习“卡住时怎么分配时间”。我给自己定的规则是：一道题如果20分钟没有新思路，立刻看题解，把思路记下来，第二天重新默写一遍。这不是自欺欺人，而是用主动回忆的方式把别人的解法变成自己的。

限时模拟阶段我用了一个很笨但很有效的方法：同样的题做三遍。第一遍当场写，第二遍隔天默写，第三遍一周后重新做。三次都顺利通过，这道题才算真正掌握。这个方法的周期比较长，但对记忆的巩固效果远超“刷完即走”。

5.4 最后一个建议：做好“解题思路笔记”而不是“代码笔记”

刷到4星这个级别，最需要积累的是思路推理链，而不是代码库。因为代码网上随处可查，但你面对一道新题时能不能想起“该用枚举中间元素+树状数组”，这才是决定成败的关键。我自己的笔记里会记录：

• 为什么想到这个方向（题干里哪个词触发的）
• 中间尝试过哪些错误思路（防止下次再走弯路）
• 复杂度优化的关键一步是什么
• 这道题对应的类似题有哪些

比如刚才那道三元组计数题，我的笔记里只写一句话：满足大小关系且带位置约束的三元组计数 → 枚举中间锚点，拆成左右两段用树状数组维护。这句话在后来遇到类似题目时，几乎0思考就能切入正确方向。

还有一个小技巧是，每周末把本周错题和卡过半小时以上的题归拢出来，把题干里的场景词换成通用模型词。比如“直播观看记录”其实就是“数组”，“优惠券叠加规则”就是“区间合并”。这一步能有效帮助你在笔试时看穿场景包装，直击算法内核。