来offer独家习题讲解 | Next larger number in a sequence
如果你正在找工作，以下文章对你有帮助：
来Offer孙老师专题 | 如何应对2017FLAG校招freeze
题目描述
Given a sequence of integers, for each number, find the index of the next higher number, which is on the right side of the current number.
给一个含有n个整型数字的数组input，对于其中每一个数字，找到其右边第一个比它大的数的位置(index)，如果不存在符合要求的数，则用-1表示。
例如：
Input: [3, 2, 1, 4, 1, 9]
Output: [3, 3, 3, 5, 5, -1]
解题思路
暴力解法往往会被很多同学忽视，而实际上它有着极为重要的作用：
从工程的角度上来讲，有一个解决方案永远都好于没有解决方案，而工程师首先需要能够有一种方法来解决问题。
从算法设计的角度上来讲，知其然更要知其所以然，所有的算法都是对暴力解法的层层优化，用一种更有效率的方法来解决问题。
在这个过程中能够体现出的观察力，分析能力才是解决问题的法宝，也是成为一个高质量的工程师能力和核心竞争力最好的体现。
首先，当我们看到这道题，我们至少应该得到一个最暴力最原始的解法。暂且称之为Naive解法。
这个最暴力的解法就是：对于每一个数组中的数，都过一遍这个数组，把我们所要找的数找到。
Solution 1: Naive解法
算法：利用两层循环。针对数组中每一个数字，以其右边作为起始位置，向后搜寻第一个比它大的数。
代码如下：
该种解法的最坏情况发生在：
当数组中的数是完全递减的时候。这样就需要n*(n-1)/2次比较。所以，Naive解法的时间复杂度是O(n^2)，额外空间复杂度是O(1)。
通过观察和分析找到已有解决方案中效率不高的步骤来进行优化。
观察的关键在于找到原有方案中效率不高的部分，一般来讲可以分为两大类：
不必要的计算
重复的计算
在这个过程中，利用观察例子来找到规律是必不可少的步骤，而用例子来帮助理解和解释问题也是最有效的方法。
我们可以通过观察例子进一步考虑如何优化时间复杂度：在基本解法中，每一个数字都被多次比较。
例如：在示例的input中，3要和2比，再和1比，然后和4比较才能得知4是3的下一个较大的数；2也需要先和1比较，再和4比较才能得到它对应的结果。
实际上，如果我们知道了2比3要小，当2和1比较时，得知1比2要小的时候，我们并不需要再将3与1进行比较了。这样的比较其实是多余的。基于这一点，我们可以进一步考虑如何优化Naive方法。
很显然，如果我们可以提前比较3与2之后，又比较了2与1，那么3和1就不需要再比较了。
从中，我们可以发现一个规律，[3, 2, 1]是一个递减的数组，当一个新的数字到达，它比当前的数要小的话，那么它一定不是当前数之前数字的结果。
我们可以借用一个stack维持一个非递增数列从而实现这样算法，移除多余的比较。基于此，我们可以得到如下解法：
Solution 2: 优化数据结构选择
额外的数据结构—stack: 利用一个stack去记录所有非递增的数列。存储这些数的index。
算法: 从左向右扫描input数组。
分成两个cases来处理：
Case 1: 如果当前栈为空或者新扫描到的数字比当前栈顶的数字要小，就把新到的数字加到栈中。
Case 2: 如果新扫描到的数字比当前栈顶要大，我们就开始从栈中pop出数字，并把pop出来的数字的对应结果记为当前数的index。
终止条件：扫描完所有的数字。栈中还剩余的数字为没有下一个较大数的数字。
代码如下：
针对数组中的每一个数，其最多入栈出栈一次。此种方法的时间复杂度是O(n)。
使用了一个额外的stack，最坏的情况是所有的数字都被压入栈。此种方法的空间复杂度也是O(n)。
自主的继续发现问题和解决问题，永远不满足于现有的解决方案是我们应有的态度。
对现有方案效率的分析可以帮助我们继续寻求更优的方法，层层推进继续尝试其它的突破口。
在面试中，如果能给出上述方法，一般来说，可以达到面试官的要求。
但是，我们能不能进一步思考，并提出一个解法，把空间复杂度也给优化了呢？
让我们回顾一下Naive解法，我们会发现，Naive解法并没有利用已经找好了的数字。如何利用已经计算过的结果是如何优化空间复杂度的关键。
我们可以试图从这一点入手，尝试使用已经得到的信息。对于每一个i]。我们可以尝试从紧邻其右边的第一个数input[j], j = i+数input[i]，假使对于所有input[j], j>i，我们已经找到答案。
我们所要做的是找到当前数input[i]所对应的答案output开始查找，如果这个数字比当前数字大，很显然当前数字的答案已经找到。
如果input[j]小于input[i]，并且input[j]并没有next larger number，很显然input[i]也不会有next larger number。
如果input[j]小于input[i]，但是input[j]存在next larger number，则说明index在j与output[j]之间的数小于input[j]，很显然这些数也会小于input[i]，那么这些数字一定会小于input[i]，我们不需要考虑这些数，直接跳到j=output[j]进行下一轮判断。
从后往前对input数组进行扫描，通过这样的一种算法，我们就可以利用已经找到的结果，从而减少时间复杂度。
Solution 3
算法：从后往前扫描，针对每一个数（index记为 i ）。Initialization： j = i + 1
Case 1: 如果input[j] > input[i]，则output[i] = j.
Case 2: 如果input[j] <= input[i]，则：
Case 2.1：如果output[j] = -1，则output[i] = -1。
Case 2.2：否则，j = output[j]。重新开始判断。
终止条件：扫描完所有input数组。
代码如下：
从上述代码可以看到，针对每一个数字，操作j = output[j]至多计算一次。同时外围的循环i也是一轮遍历。所以该算法是一个线性算法，时间复杂度亦为O(n)。
同时，由于该算法并没有使用额外的存储空间，我们可以认为其空间复杂度是O(1)。
在对基础数据结构和算法扎实的理解的基础上，通过大量的练习，思考和总结才能真正开拓思路和提高系统的分析能力。
对大家的小建议是：
不要急于尝试思维跳跃来寻求最佳解决方案，欲速而不达。
重视基本解法，从最基本的解法出发，通过多个例子来加强自己的观察能力和找到优化突破口的能力。
永远不要放弃尝试，对于现有方案时间和空间复杂度的分析是层层推进的起点。
求职，你只需要一门课程
来Offer 2017年春季班2期
3月20号正式开课
Who We Are
来Offer网 (www.laioffer.com) 由清华大学计算机系在硅谷顶级科技公司（Google, Facebook,Uber）Director & Manager级别校友组成的职业培训机构。成员中有国际信息学奥赛International Olympiad in Informatics (IOI)中国国家队教练，Facebook 最早期的中国工程师经理和中国大陆招聘工程师负责人, 高考省理科状元，Stanford, CMU, Harvard, USC 等校CS Ph.D.组成。
What We Do
用最顶尖的师资力量带出高水平的学生：让强者更强，拿到一线大公司的Offer， 让转专业的同学迅速系统提高，拿到SponsorH1B的正规公司的Offer. 拿Offer不仅仅靠算法，而是系统素质的展现，包括英语表达沟通能力，Coding质量，多线程，System Design, OO Design，以及对美国职场最基本的理解。我们不仅仅是算法培训机构，而是一个培训同学们高成功率拿到Offer的职业培训机构。
FLAG 级别 Manager Level班主任负责制，有问题直接语音问答；每班配备10+名主讲老师，精心为同学们课后答疑和 1对1 code review.
独立Online Coding训练系统 code.laioffer.com (300+最新大公司真题只对内部学员开放)
Google/Facebook engineer 上机课手把手教你编程
每月一次跟踪考试, 老师1对1修改coding
英文口语/书面的提高
一线大公司Director/Manager level的老师， 内部推荐＋面试综合技术提高
Internship level 3个月完成的实战project (可选课程)
免费重复听，直到找到工作
高成功率
高成功率是我们唯一的标准: 2013年成立以来我们已经帮助数百名同学拿到Offer，成功率稳定在 80%。 其中Google, Facebook, Uber, Box, Microsoft, Yahoo, Amazon, Indeed, Hulu, IBM 等大中型公司超过半数。真名实姓Offer榜请见www.laioffer.com
欢迎发送简历至info@laioffer.com报名
我们将在24小时内联系您