美团2016研发在线编程题复盘：大厂算法笔试高频题型与解题要点

聊到美团2016研发工程师在线编程题很多参加过当年校招的同学应该都有印象。那年的题目整体不算偏难怪但特别考验基础算法的熟练度和边界条件的敏感度和现在动不动就上树套树、后缀自动机的“硬核”笔试相比反而更接近日常工作里真正会用到的那类编码能力。这篇文章不打算做成题目答案的搬运工而是从实际答题和事后复盘的角度把这类在线编程题背后的考点、解题路径和容易踩的坑拆开讲清楚。如果你正在准备大厂研发岗的笔面试或者想系统提升算法基本功这篇文章可以当一份“美团风格在线编程题”的复习提纲来用。文中涉及的都是在线笔试里出现频率很高、且至今仍被大量公司沿用的经典题型我会把思路、代码、复杂度分析和易错点一起说清楚方便你直接照着练。1. 2016年美团在线编程题整体在考什么1.1 题目风格与考察方向那几年的美团在线笔试题目量一般控制在2到4道时间1到1.5小时语言可选C/C/Java部分年份支持Python。从题目难度分布来看第一题通常偏简单考字符串处理或数组操作属于“送分题”第二题和第三题则逐步进入数据结构和经典算法的范畴常见考点集中在数组、字符串、栈、链表、二分查找和基础动态规划上几乎不会出现特别复杂的图论或计算几何问题。这个出题风格和美团当时“快速筛选工程能力”的招聘诉求是匹配的。研发工程师日常写代码更多是处理数据清洗、接口逻辑、存储结构和业务状态流转而不是在纸上推导高深算法。所以在线编程题更看重三件事第一能不能把思路快速转换成可运行的代码第二代码能不能处理边界情况而不是只过样例第三在数据量变大时复杂度能不能扛住。这些能力恰恰是“把代码写稳”的基本功。我见过不少同学刷题只刷难题偏题结果在线笔试时反而在简单题上翻车——要么数组越界要么没考虑空输入要么时间复杂度估错导致超时。美团这类公司出在线编程题目的不是选拔“竞赛选手”而是筛掉“代码写不利索”的人。所以备考重点应该放在基础题型的熟练度上而不是一味追求难题偏题。1.2 为什么这些老题至今仍有参考价值可能有人会觉得2016年的题目太老了现在互联网公司笔试都卷出新高度。但从我最近几年的观察来看基础考点反而有回潮趋势。很多公司开始意识到纯竞赛化出题招进来的人写业务代码未必顺畅反倒是那些能把二分、栈、双指针、简单DP写得很稳的候选人上手工作更快。另一方面美团2016年这批题目本身选材就很有代表性直方图最大矩形单调栈、买卖股票贪心/DP、旋转数组二分二分变形、字符串处理双指针——这些题型在后来的字节、腾讯、阿里、百度笔试题里反复出现。你把这批题吃透等于把在线编程题的“高频基础面”覆盖了一大半。所以这篇文章虽然标题带“美团2016”但我更愿意把它当成一份“大厂在线编程经典题型复盘”来写你可以放心参考。2. 典型题目拆解从读题到AC2.1 直方图中最大矩形面积这道题在2016年前后非常流行现在也经常出现在各家公司的笔试题里。题目描述很简洁给定n个非负整数表示直方图中每个柱子的高度每个柱子宽度为1求该直方图中能够勾勒出的最大矩形面积。举个简单例子柱子高度为 [2,1,5,6,2,3]最大矩形面积是10对应高度为5和6的两个柱子组成的宽为2、高为5的矩形。刚拿到题最直接的想法是枚举。对每个柱子向左向右扩展找到第一个比它矮的柱子就能算出以当前柱子高度为矩形高的最大宽度。这个做法的时间复杂度是O(n^2)当n达到10^5级别时必然超时。面试官出这道题真正想看到的解法是单调栈。核心思路是维护一个高度递增的栈当新柱子高度小于栈顶柱子高度时说明栈顶柱子的右边界已经确定可以弹出并计算面积了。每个柱子只会入栈和出栈一次整体复杂度O(n)。public int largestRectangleArea(int[] heights) { if (heights null || heights.length 0) return 0; int n heights.length; int[] stack new int[n 1]; int top -1; int maxArea 0; for (int i 0; i n; i) { int currentHeight (i n) ? 0 : heights[i]; while (top 0 currentHeight heights[stack[top]]) { int h heights[stack[top]]; top--; int leftBound (top 0) ? stack[top] : -1; maxArea Math.max(maxArea, h * (i - leftBound - 1)); } stack[top] i; } return maxArea; }这段代码里有两个关键点要特别注意。第一在数组末尾追加一个高度为0的哨兵柱可以强制把栈里所有剩余柱子清空避免循环结束后再单独处理。第二宽度计算用的是i - leftBound - 1leftBound是当前弹出柱子左侧第一个比它矮的柱子下标i是右侧第一个比它矮的柱子下标两者之间就是能完全容纳当前高度的宽度区间。我第一次写这道题时栽在宽度计算上。很多人写成i - stack[top]这算出来的是从上个柱子到当前柱子的距离而不是弹出柱子的实际宽度。举个例子柱子高度[2,1,2]处理到第三个柱子时栈里剩下下标1高度1此时弹出下标0宽度应该是3整个数组长度如果用i - stack[top]算得到的是3-12结果就错了。2.2 买卖股票的最佳时机多次交易版这道题在美团2016年笔试题里也有类似变体属于典型的“看起来复杂、想通后很简单”的题目。描述是给定一个数组pricesprices[i]表示第i天的股票价格你可以在任意一天买入、在之后的某一天卖出且最多只能同时持有一股可以进行多次交易即卖出后才能再次买入求能获得的最大利润。很多人的第一反应是用动态规划维护状态每天手里有股票或没有股票然后做状态转移。这个思路没错但有点大材小用。仔细分析会发现只要第二天价格比第一天高就可以在这两天之间完成一次交易获取差价因为不限制交易次数所有上涨段都可以累加起来。所以贪心解法只需要遍历一次只要prices[i] prices[i-1]就把差值加到结果里。这个做法理解起来很直观一根K线图把所有上升沿的涨幅加起来就是最大利润。public int maxProfit(int[] prices) { if (prices null || prices.length 1) return 0; int profit 0; for (int i 1; i prices.length; i) { if (prices[i] prices[i - 1]) { profit prices[i] - prices[i - 1]; } } return profit; }复杂度O(n)空间O(1)代码简洁到面试官都不好意思说你写得啰嗦。但如果题目改成“只能交易一次”解法就变成动态规划了维护一个历史最低买入价minPrice同时维护一个最大利润maxProfit遍历时不断更新这两个值。这里要注意更新顺序不能反应该先更新最大利润再更新最低价因为最低价必须是当前天之前的价格不能用当天价格既当买入价又算卖出价。在线笔试里经常出现“一题多问”的情况比如第一问只能交易一次第二问不限制次数。如果只背了多次交易的贪心解法遇到限次版本就容易懵。建议把两种解法一起准备并且理解清楚为什么限制次数必须DP不限制次数的可以用贪心。2.3 寻找旋转排序数组中的最小值旋转数组是二分查找的高频考点美团2016年那批题目里也有涉及。题意是一个按升序排列的数组在某个未知点做了旋转比如 [0,1,2,4,5,6,7] 旋转成 [4,5,6,7,0,1,2]要求找到数组中的最小元素。题目有两个版本不包含重复元素和包含重复元素后者难度稍高。不重复版本的核心是二分。维护左右指针 left 和 right取中间位置 mid。如果nums[mid] nums[right]说明最小值在右半段因为左半段仍然是升序且整体大于右半段否则最小值在左半段或者就是 mid 本身。不断缩小区间直到 left 和 right 相遇。public int findMin(int[] nums) { int left 0, right nums.length - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] nums[right]) { left mid 1; } else { right mid; } } return nums[left]; }边界条件要想清楚。比如数组没有旋转即完全升序 [1,2,3,4,5]此时nums[mid] nums[right]永远为falseright会不断收窄到0最终返回nums[0]正确。比如数组只有两个元素 [2,1]mid为0nums[0] nums[1]left右移到1返回nums[1]正确。如果数组包含重复元素上述逻辑有个漏洞当nums[mid] nums[right]时无法判断最小值在哪边。比如 [1,1,1,0,1] 和 [1,0,1,1,1]mid和right相等时左半和右半都有可能含最小值。解决办法是把right左移一位即right--这样可以安全缩小范围代价是最坏情况下时间复杂度退化到O(n)。public int findMinWithDuplicates(int[] nums) { int left 0, right nums.length - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] nums[right]) { left mid 1; } else if (nums[mid] nums[right]) { right mid; } else { right--; } } return nums[left]; }这一类“二分变种”题核心不是背模板而是想清楚每次比较之后如何缩小区间、保证答案不会丢。面试官如果问“为什么等于时right--不会把最小值错过”你需要答出因为nums[mid] nums[right]说明最小值所在区间可能包含mid也可能在mid左边但right这个位置的值和mid相同把它排除掉不影响最小值的查找因为最小值仍然在[left, right-1]这个区间里。2.4 字符串翻转与单词处理字符串题在线笔试里属于“送分题”中的“赚分题”但越是简单越容易在细节上丢分。比较有代表性的一类是“反转字符串中的单词顺序”或“反转单词中的字母顺序”美团当年的题目库中也包含这类基础操作。比如输入hello world要求输出world hello。很多人的第一反应是 split 后再逆序拼接。这种方法在Java和Python里都能AC但不是最优解且在某些面试官眼里显得缺乏思考。更通用的做法是两次翻转先整体翻转整个字符串再对每个单词内部做一次翻转。这样做的好处是空间复杂度O(1)且不依赖split函数对C/C这种不擅长字符串分割的语言尤为重要。public String reverseWords(String s) { if (s null) return null; char[] arr s.toCharArray(); int n arr.length; reverse(arr, 0, n - 1); int start 0; for (int i 0; i n; i) { if (i n || arr[i] ) { reverse(arr, start, i - 1); start i 1; } } // 清理多余空格完整实现略 return new String(arr).trim().replaceAll(\\s, ); }写这道题时要特别注意两点。第一单词间可能有多个空格题目是否要求去除多余空格需要先确认第二整体翻转后单词内部的字符顺序是反的必须再对每个单词做一次局部翻转两次翻转的边界要算清楚start的更新不能错位。我建议备考时把字符串类题目集中刷一遍包括反转、回文、子串、最长公共前缀这几种基础题型。它们单独拿出来都不难但综合在一起能覆盖笔试中相当比例的“保分题”。3. 在线编程答题的实战要点3.1 先花5分钟想清楚再动手写代码在线笔试和平时在IDE里写代码完全不同没有调试器、没有单步跟踪甚至有些平台连报错信息都很模糊。很多同学一看到题目就急着敲键盘结果写到一半发现思路不对只能推倒重来白白浪费大量时间。合理的时间分配应该是每道题先用3到5分钟读题、画样例、明确输入输出再花2分钟想清楚时间复杂度和边界条件确认无误后开始写代码。一个我反复验证有效的习惯是写代码前先在注释里写下核心思路哪怕只有一句话。比如“用单调栈维护递增序列遇到小值就弹出计算面积”。这不仅是理清思路更能在写代码时提醒自己不要跑偏。遇到比较复杂的逻辑直接在纸上或者草稿区画一下示例的运行流程比对着空白的编辑器硬想效率高很多。3.2 数据范围决定算法选型在线编程题一般会给出数据范围提示或者你可以从样例规模反推。在没有提示的情况下有几个经验值可以记住n在1000以内O(n^2)基本可以接受n到10^5O(n^2)必超时至少要O(n log n)或O(n)n到10^6或以上优先想O(n)甚至O(log n)的解法。举个例子直方图最大矩形如果n是100暴力枚举也能过但美团笔试里n通常是10^5这时候你就要想到单调栈。在线编程题的超时判定很严格不是“能跑出结果”就行而是要在限定时间内跑完所有测试用例。选错算法等于直接送掉一道题这个亏我早期吃得太多了。3.3 处理好输入输出细节有些在线笔试平台对输入输出有严格要求比如一组数据多行读取、每行结尾可能有空格、需要输出到标准输出而不是返回值。虽然美团2016年那批在线题大多采用“核心代码模式”只需要实现函数但也有部分题目需要自己处理输入。建议平时练习时两种模式都适应尤其是Python选手input()读取时的去空格、split()的边界处理都要做到条件反射。另一个容易忽略的坑是数据溢出。Java里int最大约2.1*10^9如果题目数据范围是10^9级别的数量级相加结果就可能溢出int。涉及求和、乘积的场景直接声明为long更稳妥C同理。用Python的同学不用担心这个问题但如果面试官要求你分析复杂度或手写代码还是要能说出“这里用long避免溢出”的意识。3.4 代码风格是隐性评分点很多在线编程平台会提供代码给人眼review代码风格在面试进程里会影响面试官对你的判断。变量命名尽量用有意义的英文不要用a、b、c、tmp这类含义不明的缩写核心逻辑加上简短注释不要写一长串几百行的函数能拆成辅助函数就拆开。这些看似不重要的细节在“判断候选人是否具备工程素养”这件事上权重比你想象的要高。我见过一份笔试代码算法完全正确AC了所有测试用例但整个文件只有三个变量名a、b、c。面试官看完直接评价“可读性差难维护”。这不是吹毛求疵研发工作里大部分代码是给别人看的代码风格是入门基本功。4. 高频坑点与排查心得4.1 边界条件自查清单在线笔试最常见的失分原因不是不会做而是忘记处理边界条件。我整理了一份高频自查清单每次提交前过一遍能显著减少“样例过但AC不了”的惨案空数组、空字符串是否处理数组只有一个元素是否符合预期所有元素相同是否会导致死循环或越界输入中存在负值或0是否影响逻辑涉及到数组下标减一或加一的位置是否可能越界求和或乘积是否溢出int范围输出格式是否与题目要求完全一致包括换行和空格这些检查点不需要每个都验证但扫一眼能帮你避开八成以上的低错。4.2 常见运行时错误的根因分析很多在线平台提交后报“Runtime Error”但不会告诉你具体原因。结合我踩过和看别人踩过的坑这类错误八成是数组越界或栈溢出。数组越界常见于二分查找的mid 1写成了mid或者循环条件里使用了而不是导致right或left超出范围。递归栈溢出则常见于深度优先搜索或递归实现的快速排序当递归深度达到10^5以上时默认栈空间很容易爆。遇到大数据量的递归题目优先考虑用显式栈或者迭代实现。还有一种隐蔽的运行时错误是除零。比如用双指针时计算中间位置用了left (right - left) / 2这本身没问题但如果数据里包含负数且除数是0就会直接崩溃。虽然笔试题目一般不会出现这种坑但做题时仍要留意分母是否恒正。4.3 超时的排查思路提交后报“Time Limit Exceeded”先不要急着改代码逻辑。按照这个顺序排查第一步看是不是死循环。检查循环里left和right的更新是否真的让区间在缩小特别是二分和双指针很容易出现left mid导致区间不缩小的情况。第二步看时间复杂度是否达标。如果题目数据量是10^5你却用了两层嵌套循环那再优化局部也没用必须换算法。第三步看是否频繁创建对象导致GC压力。比如循环内用了new ArrayList或StringBuilder在数据量大时会显著拖慢速度尽量复用容器。我曾经在一次模拟笔试里用Java写字符串翻转在循环里反复调用substring创建新字符串数据量一到10^5就直接超时。后来改成StringBuilder或char数组速度提升了十几倍。在线编程的环境和本地不同平台性能参差不齐能写O(n)就不要写O(n log n)能用基本类型就不要用包装类。4.4 从样例到AC的调试技巧在线笔试没有断点调试能力但有一些替代手段。遇到样例不过的情况先从输入入手手动演算一遍题目给的示例确认自己对题意的理解没有偏差。然后在小规模测试用例上模拟运行输出中间结果。很多平台支持“输出调试法”即临时在代码里加打印语句把关键中间变量打印出来提交时再删掉。不要觉得这招太笨在不能打断点的环境下这是最高效的定位方式。如果你提交后只显示“答案错误”而没有具体用例可以用暴力解法写一个“对拍器”对于小规模随机数据比较暴力解和优化解的输出是否一致不一致的地方就是bug所在。这个方法我在备赛和实际笔试复盘里反复使用定位问题的速度远超肉眼查代码。5. 备赛与长期能力提升建议5.1 备考节奏怎么安排如果离笔试只有一到两周建议按题型模块复习而不是按题目顺序乱刷。可以把高频题型分成数组、字符串、栈队列、链表、树、排序搜索、动态规划、贪心、双指针、二分查找这十大类每天攻克一到两类。每类挑选3到5道经典题做到能默写核心解题模板同时理解模板的适用条件和边界处理。一个月以上的长线备赛则要把重点放在“一题多解”和“举一反三”上。比如直方图最大矩形不仅要会单调栈还要能说出它的变体最大矩形面积、接雨水、滑动窗口最大值这些题目本质都跟“单调性”有关。学一道题时花20分钟想想它可以怎么变形比刷10道同类题更有效。5.2 笔试之外的算法价值聊回美团2016研发工程师在线编程题表面上看只是几道算法题但它背后筛选的是工程思维和基础功底。这些年我带过的应届生里编程题成绩好的人上手业务代码的速度普遍更快因为他们在处理边界、拆分逻辑、预估复杂度这些方面有意识。这也是为什么即使工作多年我仍然建议一线研发保持刷题习惯——不是为了面试而是为了保持对代码质量的敏感度。我个人在实际操作中的一个体会是在线编程题的成绩好坏往往不取决于你刷过多少道题而取决于你对每一道做过的题理解到多深。拿到一道新题能不能一眼识别出它的考点、能不能快速写出正确边界条件下的代码才是真正的核心竞争力。准备这类题目的时候宁可少做十道题也要把每一道题的“为什么”彻底想明白把该踩的坑提早踩一遍笔试的时候就会从容很多。