算法学习（3）：单调栈

栈是一种很常用的数据结构，最大的特点就是只能在一端进行操作。Java中的集合提供了一个接口Deque来表示栈结构，如下语句：

Deque stack = new ArrayDeque<>();

至于为啥不用Stack类，请看下面这篇文章：
Java 程序员，别用 Stack？！

那么，单调栈又是什么呢？很简单，就是普通的栈加一个限定条件：栈内元素单调递增或单调递减。单调栈并不是一个Java集合中现成的容器，而是需要在编码中手动控制栈内元素的单调性。举个例子：有一个栈，用右边这个数组（右端是栈顶）来表示：【5，3，2，1】，目前来看，栈内的元素从栈底到栈顶是单调递减的，满足单调栈的属性，现在又来了一个4，那么这个4如果直接入栈，就会破坏单调栈的属性，为了保持单调，就需要依次将栈顶的1，2，3出栈，再将4入栈，此时栈内元素是【5，4】，依然满足单调栈的属性。所以说，栈内元素的单调性是人为保证的，那就是：当遇到要入栈的元素破坏了栈内的单调性，就需要将栈内的元素出栈一部分，直到满足单调性。

很多网上的概念以栈顶到栈底的递增或递减来定义单调递增栈或单调递减栈，有的相反。其实大可不必死记这些概念，以实际情况来保证是递增还是递减。

最后，来看下单调栈的使用场景：单调栈专门用来优化一种场景，就是快速找到数组中比当前元素大或者小的元素。至于怎么优化的，接下来通过LeetCode几道题来看。

1、LeetCode 496. 下一个更大元素 I

给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。

请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。

该题使用暴力双重循环也能解决问题，但是时间复杂度为O(N²)，我们可以使用单调栈的性质将时间复杂度降到O(N)，我们以示例num2 = 【1，3，4，2】来模拟单调栈的操作。
先建一个栈，然后依次遍历数组中的元素：
a. 走到num2的元素1，此时栈为空，直接将元素1的下标0入栈，栈内元素是【0】；
b. 走到num2的元素3，此时栈不空，判断栈顶元素（下标0）对应的值1，跟3的大小关系，发现1比3小，1 需要出栈，1出栈的同时也说明了：对于1这个元素来说，已经找到了第一个比它大的元素，那么我们可以将这个记录下来，比如map.put(0，3)，表示下标0代表的值1的第一个比它大的元素是3.