单调栈

用法

 给你一个数组，要求你找到数组中每个元素左边第一个比他大的数和右边第一个比它大的数，举个例子，数组[3,5,2,1,6]，3左边比他大的没有，右边比他大的是5；5左边比它大的没有，右边比他大的是6；2左边比它大的是5，右边比他大的是6；1左边比他大的是2，右边比他大的是6；6左边比他大的没有，右边比它大的没有

单调栈应用

 上面的问题，直接遍历可以，但是如果利用单调栈来做，可以保证时间复杂度为O(n)。首先说明一下什么是单调栈，单调栈就是栈内元素都是严格单调递增或单调递减的，根据题目具体情况。  看一下单调栈的工作过程（这里是单调递减栈，就是从栈底到栈顶是递减的），还是以nums = [3,5,2,1,6]为例，单调栈存的是数组下标。  首先，栈空，所以下标0直接入栈；  然后到了下标1，因为nums[stack.peek()] < nums[1]，所以栈顶元素出栈，在出栈的时候记录是什么值让我出栈的，在这里是下标值1让栈顶出栈，所以栈顶元素的右边比他大的数的下标就是1，然后看当前值出栈前，在栈内排在我下面的值是谁，因为0下面没有值，所以是空，因此nums[0]的左边比他大的数没有，右边比它大的数是nums[1]；  继续，因为nums[1] > nums[2]，所以2直接进栈；  3也直接进栈，此时栈内从栈底到栈顶依次是1,2,3；  然后来到了4，因为nums[stack.peek()] < nums[4]，所以stack.pop()，3出栈，出栈的时候开始记录，在栈内，3底下的数是2，所以3左边比他大的数的下标是2，因为4要进栈，导致3出栈，所以4是3右边比它大的数的下标；  因为nums[stack.peek()] < nums[4]，所以还要继续出栈，此时出栈的值是2，按照之前的规则，2左边比他大的数的下标就是1，2右边比它大的数的下标就是4；  因为nums[stack.peek()] < nums[4]，所以依然继续出栈，此时出栈的值是1，1左边比它大的数没有，右边比它大的数的下标是4；  现在栈是空的，所以4直接进栈了，然后到了数组的边界，因此栈内剩下的所有值都直接弹出，并且按照之前的规则，记录每一个值，因为没有元素要进栈，而是便利到了数组结尾导致他们要出栈，所以栈内所有的值右边比它大的数的下标都是空，左边比它大的数的下标就是在栈内，他们下面的数。对于当前栈内情况来看，4左边比它大的数的下标和右边比它大的数的下标都是空。