Algorithm
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)。在对基础数据结构和算法扎实的理解的基础上，通过大量的练习，思考和总结才能真正开拓思路和提高系统的分析能力。
对大家的小建议是：
不要急于尝试思维跳跃来寻求最佳解决方案，欲速而不达。
重视基本解法，从最基本的解法出发，通过多个例子来加强自己的观察能力和找到优化突破口的能力。
永远不要放弃尝试，对于现有方案时间和空间复杂度的分析是层层推进的起点。
图片来自网络，版权属于原作者