如果你翻过牛客网上京东的历年真题大概率会看到这套“京东2016研发工程师编程题二”。它一共三道题一道环形士兵可见对核心是单调栈一道小球反弹纯数学推导一道钓鱼比赛考概率模型。题目看着都不难但当年笔试现场能全做对的人真的不多。这篇博文就把这三道题掰开揉碎讲一遍适合正在准备大厂校招编程题的同学也适合想补一补单调栈和概率基础的开发者。1. 这套题的整体情况与考点拆解1.1 京东2016校招笔试是个什么风格2016年前后京东校招技术岗笔试已经全面转向在线OJ答题题型以选择题加编程题为主。编程题部分不会故意出偏题怪题更看重基础数据结构和数学能力。这套“编程题二”的定位就是典型校招难度不需要复杂的算法知识但需要你在有限时间内写出逻辑自洽、边界正确的代码。三道题分别落在三个完全不同的知识域题目核心考点难度出现频率保卫方案单调栈、环形数组处理、重复元素合并中等偏上很多大厂都考过类似题抛小球等比数列求和、无穷级数简单低但思维很典型钓鱼比赛概率计算、几何分布、随机变量中等概率题年年有为什么这套题值得专门拿出来写因为它把“数据结构题”“数学题”“概率题”各放了一道基本就是校招编程题的缩影。你看完这篇至少能掌握一套处理环形单调栈问题的方法论以及概率题的一个通用建模套路。1.2 做题顺序建议我个人的习惯是先做抛小球这类纯数学题几分钟搞定稳定拿分再做钓鱼比赛公式推清楚也能快速写出来最后留最多时间给保卫方案因为它最考验代码功底和边界处理。不建议一上来就啃保卫方案。万一卡在重复高度合并的细节上后面两道简单的题就没时间写了。笔试不是竞赛得分效率才是第一位的。2. 保卫方案把单调栈考到极致的环形可见对问题2.1 题目到底在说什么这道题的原题背景是“战争游戏里的士兵站岗”但剥离背景后问题非常清晰有一圈士兵每个士兵有一个高度值。两个士兵能够互相看见当且仅当这两个士兵之间的所有士兵的高度都不高于这两个士兵中较矮的那个。求整个环形队列中能互相看见的士兵对数。举个例子如果三个士兵高度分别是 5、1、5环形排列。1 和左边 5 相邻能看见1 和右边 5 相邻能看见左边 5 和右边 5 之间隔着 1而 1 的高度小于等于 5所以两个 5 也能互相看见。因此答案是 3 对。这道题有几个关键点一是环形二是高度可能重复三是数据规模可能很大。当年牛客网上这题的 n 可以到 10 的 6 次方级别O(n^2) 的枚举稳稳超时。2.2 暴力解法为什么不行最直观的暴力做法是枚举所有士兵对然后检查它们之间是否满足“所有士兵都不高于较矮者”。听起来简单但复杂度是 O(n^2) 甚至 O(n^3)。当 n 是 10 的 6 次方时这种解法在在线判题系统里连一组数据都跑不完。再说环形数组的“两个方向”问题也很容易把自己绕晕。你要同时检查顺时针和逆时针两个方向吗如果两个方向都能看见这一对算一次还是两次暴力的思路越想越复杂这就是为什么需要更聪明的数据结构。2.3 用单调栈解环形可见对的完整思路单调栈的核心应用场景之一就是“找每个元素左边第一个比它大的位置”或“右边第一个比它大的位置”。这道题的可见性恰好和这个有关。先说一个结论如果我们把士兵按环形排列那么每个士兵左侧连续一段“比它矮”的士兵以及右侧第一个比它高的士兵都是它能看见的对象。但这里有个麻烦重复高度。如果有两个相同高度的士兵相邻或相隔一段连续不高于这个高度的区域它们彼此也能互相看见而且不能重复计数。标准的解法分三步第一步找到整个环形数组中最大高度的位置。为什么从最大值开始因为最大值不会被任何士兵挡住把它当作起点就可以把环形数组“剪开”成一个线性数组避免扫描一圈回来时的重复计数。第二步维护一个从栈底到栈顶严格递减的单调栈。栈里存两个信息士兵高度和该高度连续出现的次数。为什么要合并次数因为相同高度的士兵在可见性上是等价的可以一次处理一批减少计算量。第三步从左到右遍历展开后的数组。每遇到一个元素先看它是否比栈顶高度高。如果高就说明栈顶元素“遇到”了它右边第一个比自己高的元素可以结算栈顶元素产生的可见对数了。结算时的贡献公式是假设出栈的高度出现了 k 次。这 k 个士兵每一个都能和左侧第一个更高的士兵形成 k 对和右侧当前这个更高的士兵形成 k 对所以是 2k 对。这 k 个士兵彼此之间因为高度相同且中间没有比它们更高的互相可见所以是 C(k, 2) 对。所以一次出栈贡献 2k C(k, 2)。最后遍历结束时栈里还有剩余元素需要单独清算。这里有一个非常容易写错的小细节如果栈中只剩下两个元素说明倒数第二个士兵的“左右两侧”其实是同一个最大值那么它只能贡献 k 对而不是 2k 对。我在下文代码里会专门处理这个分支。2.4 完整代码与关键点逐行解析下面是我整理后的可运行代码核心逻辑对齐了常见题解的标准写法#include iostream #include vector #include stack using namespace std; int main() { int n; while (cin n) { vectorlong long h(n); for (int i 0; i n; i) cin h[i]; if (n 2) { cout 0 endl; continue; } // 找到最大值的位置作为环形数组的起点 int maxIdx 0; for (int i 1; i n; i) { if (h[i] h[maxIdx]) maxIdx i; } // 单调递减栈栈底到栈顶高度递减 // pair 的 first 是高度second 是该高度出现的次数 stackpairlong long, long long st; st.push({h[maxIdx], 1}); long long ans 0; // 从最大值的下一个位置开始绕一圈处理所有其他士兵 for (int step 1; step n; step) { long long cur h[(maxIdx step) % n]; // 当前高度大于栈顶说明栈顶元素右侧出现更高元素需要结算 while (!st.empty() cur st.top().first) { long long k st.top().second; st.pop(); ans 2LL * k; // 左侧更高元素 右侧更高元素 ans k * (k - 1) / 2; // 相同高度之间互相可见 } // 相等高度合并次数 if (!st.empty() cur st.top().first) { st.top().second; } else { st.push({cur, 1}); } } // 清算栈中剩余元素 // 先处理栈中大于两个元素的情况 while (st.size() 2) { long long k st.top().second; st.pop(); ans 2LL * k; ans k * (k - 1) / 2; } // 栈中只剩两个元素时弹出元素左右两侧是同一个最大值只贡献 k 对 if (st.size() 2) { long long k st.top().second; st.pop(); ans k; // 与栈底最大值之间的可见对 ans k * (k - 1) / 2; // 相同高度内部可见对 long long k2 st.top().second; ans k2 * (k2 - 1) / 2; // 多个最大值之间的可见对 } else if (st.size() 1) { // 只剩最大值本身只需考虑重复最大值之间的组合 long long k st.top().second; ans k * (k - 1) / 2; } cout ans endl; } return 0; }这里的代码有两个地方是绝大多数人第一次写会踩坑的第一个是清算阶段。很多人喜欢把所有剩余元素统一按“贡献 2k C(k,2)”处理结果遇到重复最大值或最后一个元素时多算。我见过的错误答案里至少有一半是死在这个细节上。第二个是答案可能非常大。n 到 10 的 6 次方时最大可见对数接近 n 的平方超过 int 范围所以 ans 和计数都要用 long long。2.5 关于重复高度和环形处理的一些心得这道题如果不考虑重复高度其实有一个更简洁的结论n 个互不相同的士兵排成环可见对数量恒等于 2n - 3。我第一次看到这个结论时觉得神奇但仔细一想就明白了最大值能看到其他所有 n-1 个士兵其他每个士兵至少能看到左右两个方向各一个“最近的更高者”这些边加在一起恰好构成一棵形似“双射”的结构。但一旦出现重复高度这个简洁结论就失效了。你不能再把相同高度当独立元素处理而是要把它们合并成一个组。这也是我推荐使用单调栈合并次数方案的原因它能统一处理重复和不重复两种情况。如果你在面试中遇到这道题建议先讲清楚“找到最大值破环”“单调栈维护递减序列”“相同高度合并”这三个核心点再写代码。面试官更看重你是否理解为什么这样做不会重复计数。3. 抛小球等比数列求和别被“无限反弹”吓住3.1 题目的本质这道题原文大概是说小东和朋友在楼上抛小球给了几个球的初始高度每个球落地后会反弹每次弹起的高度是上一次的一半问从开始下落到最终停止小球一共经过了多少路程。很多人第一反应是被“无限反弹”吓住觉得是不是要模拟到天荒地老。实际上这是一个非常标准的无穷等比数列求和问题。你只需要抓住一个点第一次下落是单向的之后每一次“弹起再落下”都是对称的。3.2 数学推导过程设小球初始高度为 h。它第一次下落经过 h。第一次弹起高度为 h/2然后落回地面这一上一下总共经过 2 * 京东2016校招编程题解析：单调栈、等比数列与概率模型
如果你翻过牛客网上京东的历年真题大概率会看到这套“京东2016研发工程师编程题二”。它一共三道题一道环形士兵可见对核心是单调栈一道小球反弹纯数学推导一道钓鱼比赛考概率模型。题目看着都不难但当年笔试现场能全做对的人真的不多。这篇博文就把这三道题掰开揉碎讲一遍适合正在准备大厂校招编程题的同学也适合想补一补单调栈和概率基础的开发者。1. 这套题的整体情况与考点拆解1.1 京东2016校招笔试是个什么风格2016年前后京东校招技术岗笔试已经全面转向在线OJ答题题型以选择题加编程题为主。编程题部分不会故意出偏题怪题更看重基础数据结构和数学能力。这套“编程题二”的定位就是典型校招难度不需要复杂的算法知识但需要你在有限时间内写出逻辑自洽、边界正确的代码。三道题分别落在三个完全不同的知识域题目核心考点难度出现频率保卫方案单调栈、环形数组处理、重复元素合并中等偏上很多大厂都考过类似题抛小球等比数列求和、无穷级数简单低但思维很典型钓鱼比赛概率计算、几何分布、随机变量中等概率题年年有为什么这套题值得专门拿出来写因为它把“数据结构题”“数学题”“概率题”各放了一道基本就是校招编程题的缩影。你看完这篇至少能掌握一套处理环形单调栈问题的方法论以及概率题的一个通用建模套路。1.2 做题顺序建议我个人的习惯是先做抛小球这类纯数学题几分钟搞定稳定拿分再做钓鱼比赛公式推清楚也能快速写出来最后留最多时间给保卫方案因为它最考验代码功底和边界处理。不建议一上来就啃保卫方案。万一卡在重复高度合并的细节上后面两道简单的题就没时间写了。笔试不是竞赛得分效率才是第一位的。2. 保卫方案把单调栈考到极致的环形可见对问题2.1 题目到底在说什么这道题的原题背景是“战争游戏里的士兵站岗”但剥离背景后问题非常清晰有一圈士兵每个士兵有一个高度值。两个士兵能够互相看见当且仅当这两个士兵之间的所有士兵的高度都不高于这两个士兵中较矮的那个。求整个环形队列中能互相看见的士兵对数。举个例子如果三个士兵高度分别是 5、1、5环形排列。1 和左边 5 相邻能看见1 和右边 5 相邻能看见左边 5 和右边 5 之间隔着 1而 1 的高度小于等于 5所以两个 5 也能互相看见。因此答案是 3 对。这道题有几个关键点一是环形二是高度可能重复三是数据规模可能很大。当年牛客网上这题的 n 可以到 10 的 6 次方级别O(n^2) 的枚举稳稳超时。2.2 暴力解法为什么不行最直观的暴力做法是枚举所有士兵对然后检查它们之间是否满足“所有士兵都不高于较矮者”。听起来简单但复杂度是 O(n^2) 甚至 O(n^3)。当 n 是 10 的 6 次方时这种解法在在线判题系统里连一组数据都跑不完。再说环形数组的“两个方向”问题也很容易把自己绕晕。你要同时检查顺时针和逆时针两个方向吗如果两个方向都能看见这一对算一次还是两次暴力的思路越想越复杂这就是为什么需要更聪明的数据结构。2.3 用单调栈解环形可见对的完整思路单调栈的核心应用场景之一就是“找每个元素左边第一个比它大的位置”或“右边第一个比它大的位置”。这道题的可见性恰好和这个有关。先说一个结论如果我们把士兵按环形排列那么每个士兵左侧连续一段“比它矮”的士兵以及右侧第一个比它高的士兵都是它能看见的对象。但这里有个麻烦重复高度。如果有两个相同高度的士兵相邻或相隔一段连续不高于这个高度的区域它们彼此也能互相看见而且不能重复计数。标准的解法分三步第一步找到整个环形数组中最大高度的位置。为什么从最大值开始因为最大值不会被任何士兵挡住把它当作起点就可以把环形数组“剪开”成一个线性数组避免扫描一圈回来时的重复计数。第二步维护一个从栈底到栈顶严格递减的单调栈。栈里存两个信息士兵高度和该高度连续出现的次数。为什么要合并次数因为相同高度的士兵在可见性上是等价的可以一次处理一批减少计算量。第三步从左到右遍历展开后的数组。每遇到一个元素先看它是否比栈顶高度高。如果高就说明栈顶元素“遇到”了它右边第一个比自己高的元素可以结算栈顶元素产生的可见对数了。结算时的贡献公式是假设出栈的高度出现了 k 次。这 k 个士兵每一个都能和左侧第一个更高的士兵形成 k 对和右侧当前这个更高的士兵形成 k 对所以是 2k 对。这 k 个士兵彼此之间因为高度相同且中间没有比它们更高的互相可见所以是 C(k, 2) 对。所以一次出栈贡献 2k C(k, 2)。最后遍历结束时栈里还有剩余元素需要单独清算。这里有一个非常容易写错的小细节如果栈中只剩下两个元素说明倒数第二个士兵的“左右两侧”其实是同一个最大值那么它只能贡献 k 对而不是 2k 对。我在下文代码里会专门处理这个分支。2.4 完整代码与关键点逐行解析下面是我整理后的可运行代码核心逻辑对齐了常见题解的标准写法#include iostream #include vector #include stack using namespace std; int main() { int n; while (cin n) { vectorlong long h(n); for (int i 0; i n; i) cin h[i]; if (n 2) { cout 0 endl; continue; } // 找到最大值的位置作为环形数组的起点 int maxIdx 0; for (int i 1; i n; i) { if (h[i] h[maxIdx]) maxIdx i; } // 单调递减栈栈底到栈顶高度递减 // pair 的 first 是高度second 是该高度出现的次数 stackpairlong long, long long st; st.push({h[maxIdx], 1}); long long ans 0; // 从最大值的下一个位置开始绕一圈处理所有其他士兵 for (int step 1; step n; step) { long long cur h[(maxIdx step) % n]; // 当前高度大于栈顶说明栈顶元素右侧出现更高元素需要结算 while (!st.empty() cur st.top().first) { long long k st.top().second; st.pop(); ans 2LL * k; // 左侧更高元素 右侧更高元素 ans k * (k - 1) / 2; // 相同高度之间互相可见 } // 相等高度合并次数 if (!st.empty() cur st.top().first) { st.top().second; } else { st.push({cur, 1}); } } // 清算栈中剩余元素 // 先处理栈中大于两个元素的情况 while (st.size() 2) { long long k st.top().second; st.pop(); ans 2LL * k; ans k * (k - 1) / 2; } // 栈中只剩两个元素时弹出元素左右两侧是同一个最大值只贡献 k 对 if (st.size() 2) { long long k st.top().second; st.pop(); ans k; // 与栈底最大值之间的可见对 ans k * (k - 1) / 2; // 相同高度内部可见对 long long k2 st.top().second; ans k2 * (k2 - 1) / 2; // 多个最大值之间的可见对 } else if (st.size() 1) { // 只剩最大值本身只需考虑重复最大值之间的组合 long long k st.top().second; ans k * (k - 1) / 2; } cout ans endl; } return 0; }这里的代码有两个地方是绝大多数人第一次写会踩坑的第一个是清算阶段。很多人喜欢把所有剩余元素统一按“贡献 2k C(k,2)”处理结果遇到重复最大值或最后一个元素时多算。我见过的错误答案里至少有一半是死在这个细节上。第二个是答案可能非常大。n 到 10 的 6 次方时最大可见对数接近 n 的平方超过 int 范围所以 ans 和计数都要用 long long。2.5 关于重复高度和环形处理的一些心得这道题如果不考虑重复高度其实有一个更简洁的结论n 个互不相同的士兵排成环可见对数量恒等于 2n - 3。我第一次看到这个结论时觉得神奇但仔细一想就明白了最大值能看到其他所有 n-1 个士兵其他每个士兵至少能看到左右两个方向各一个“最近的更高者”这些边加在一起恰好构成一棵形似“双射”的结构。但一旦出现重复高度这个简洁结论就失效了。你不能再把相同高度当独立元素处理而是要把它们合并成一个组。这也是我推荐使用单调栈合并次数方案的原因它能统一处理重复和不重复两种情况。如果你在面试中遇到这道题建议先讲清楚“找到最大值破环”“单调栈维护递减序列”“相同高度合并”这三个核心点再写代码。面试官更看重你是否理解为什么这样做不会重复计数。3. 抛小球等比数列求和别被“无限反弹”吓住3.1 题目的本质这道题原文大概是说小东和朋友在楼上抛小球给了几个球的初始高度每个球落地后会反弹每次弹起的高度是上一次的一半问从开始下落到最终停止小球一共经过了多少路程。很多人第一反应是被“无限反弹”吓住觉得是不是要模拟到天荒地老。实际上这是一个非常标准的无穷等比数列求和问题。你只需要抓住一个点第一次下落是单向的之后每一次“弹起再落下”都是对称的。3.2 数学推导过程设小球初始高度为 h。它第一次下落经过 h。第一次弹起高度为 h/2然后落回地面这一上一下总共经过 2 *