单调栈问题

首先什么是单调栈？并不是栈中的元素是单调的**而是指出栈的序列是单调的，所以分为单增栈和单减栈。
单增栈的实现思路：当栈为空，或者加入的元素大于栈顶元素时，将栈中比当前小的数据一次弹出，当加入数据小于栈定元素时，则直接进栈。
单减栈相反在此就不再叙述，接下来是单调栈的模板：

stack<int> st;
//此处一般需要给数组最后添加结束标志符，具体下面例题会有详细讲解
for (遍历这个数组)
{
	while(stack.isempty || 这个数>stack.peek()){
	    栈顶元素更新
	    更新结果
	}
	加入栈中
}

我们可以发现单调栈在解决
比当前元素更大的下一个元素
比当前元素更大的前一个元素
比当前元素更小的下一个元素
比当前元素更小的前一个元素
时有显著的优势，接下来我们来举几个例题：详解

leetCodeT739每日温度：

---

思路分析：其实我们分析可得，就是要找到比当前气温高的日期（下标），如果我们暴力求解时间复杂度会比较高，我们采用单调栈的方法，注意我们是将气温对应的下标压入栈中，而不是气温，具体代码如下：

public static int[] dailysTemperature(int [] T) {
		Stack<Integer> temp = new Stack<>();
		int res[] = new int[T.length];//用于存储答案
		for(int i=0;i<T.length;i++) {
		//比较的是气温，存入的是下标的差值
			while(!temp.empty() && T[i] > T[temp.peek()]) {
				int index = temp.pop();
				res[index] = i - index;
			}
			temp.push(i);
		}
		return res;
	}

leetCodeT496下一个更大元素：

给定两个没有重复元素的数组nums1 和nums2，其中nums1是nums2的子集。找nums1中每个元素在nums2中的下一个比其大的值。
nums1中数字x的下一个更大元素是指x在nums2中对应位置的右边的第一个比x大的元素。如果不存在，对应位置输出 -1 。

示例:

输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
    对于num1中的数字4，你无法在第二个数组中找到下一个更大的数字，因此输出 -1。
    对于num1中的数字1，第二个数组中数字1右边的下一个较大数字是 3。
    对于num1中的数字2，第二个数组中没有下一个更大的数字，因此输出 -1。

---

思路分析：其实我们不难发现，这也是一个寻找下一个更大数的题目，所以我们仍然使用单调栈，此题我们可以将nums2看作单调栈，用哈希表存储nums1，当我们找到nums【i】的下一个更大数时，我们看看nums1中有没有对应的数，有的话就找到对应的答案，这样复杂夫o（n）遍历nums2数组：
注意此题，我们要存储的是值，而不是值对应的下标

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Stack<Integer> stack = new Stack<>();
		int res[] = new int[nums1.length];
		Map<Integer,Integer> map = new HashMap<>();
		for(int i=0;i<nums1.length;i++) {
			map.put(nums1[i], i);/利用值找到对应的下标
			res[i] = -1;//初始化res，没有找到就是-1
		}
		for(int i=0;i<nums2.length;i++) {
			while(!stack.empty()&&nums2[i]>stack.peek()) {
				int x = stack.pop();
				if(map.containsKey(x)) {
					res[map.get(x)] = nums2[i];
				}
			}
			stack.push(nums2[i]);
		}
		return res;
    }
}