单调栈模板和应用例题
栈的特征是先进后出，单调栈说明是按照大小顺序进行排序等，下面就来详细说说这类问题的解法。得出一个清晰地模板。
单调栈模板就一句话：Next Greater Number
既然是下一个更大的元素，那从数组尾部逆序遍历，这样结合入栈出栈的顺序，会带来极大的方便，代码统一，更加接近所谓的单调栈模板。
单调栈模板
- 从后到前逆序遍历目标数组
- 利用单调栈的单调递减性来决定栈顶元素是否需要出栈。
- 重点：以栈是否为空来作为是否满足题目条件的依据进行处理。不为空说明符合条件，为空说明栈里之前没有一个元素满足条件。比如，由于是逆序，说明当前元素之后没有任何元素大于它。
- 入栈。
- 何时出栈：如果此时的新元素大于栈顶元素，那么此时如果新元素入栈，就不符合单调递减性了。此时需要将栈顶元素循环弹出，直到符合单调递减性为止。从栈底到栈顶可以是：
4,3,2,1这类。 - 何时入栈：满足单调递减性就可以入栈。
这里满足单调递减性存在两种情况，栈被清空，或栈顶元素大于新元素。此时新元素入栈，满足单调递减性。
应用例题1：739. 每日温度
1. 题目说明
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]示例 2:
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]示例 3:
输入: temperatures = [30,60,90]
输出: [1,1,0]提示：
-
1 <= temperatures.length <= 105 -
30 <= temperatures[i] <= 100
2. 解答分析
-
利用单调栈进行解答，逆序遍历数组，判断栈是否为空来作为当前元素是否有下一个更大元素的依据。
-
本题中是
从小到大对数组进行排序，最后的答案数组返回的是栈顶元素位置与当前元素i的差值。
3. 具体代码
class Solution {
//《单调栈模板方法》：逆序遍历数组，然后判断栈是否为空来作为当前元素是否有下一个更大元素的依据。
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] res = new int[n];
Stack<Integer> stack = new Stack<>();
for (int i = n - 1; i >= 0; i--) {
while (!stack.isEmpty() && temperatures[stack.peek()] <= temperatures[i]) {
stack.pop();
}
//只有这一步会变，其他步骤是相对固定的。但也是以栈是否为空来作为判断是否满足题目要求的条件
res[i] = stack.isEmpty() ? 0 : stack.peek() - i;
stack.push(i);//如果当前的栈为空，或者说是此时的元素较栈顶元素小
}
return res;
}
}
-
复杂度分析：
-
时间复杂度：
这段代码的时间复杂度为O(n)，其中n是温度数组的长度。 在循环中，我们逆序遍历温度数组，每个元素最多入栈一次，出栈一次。入栈和出栈的时间复杂度都是O(1)。因此，整个算法的时间复杂度是O(n)。
-
空间复杂度：
n即为温度数组的长度，引入栈来存储元素的索引。
-
应用例题2：496. 下一个更大元素 I
1. 题目说明
nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。
给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。
对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。
返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。
示例 1：
输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
输出：[-1,3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
- 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
- 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。提示：
-
1 <= nums1.length <= nums2.length <= 1000 -
0 <= nums1[i], nums2[i] <= 104 -
nums1和nums2中所有整数 互不相同 -
nums1中的所有整数同样出现在nums2中
2. 解答分析
-
还是一样的套路，在单调栈的基础上借助额外的数据结构
HashMap,可以存错遍历过程中所有元素的下一个更大值。最后在遍历子数组从HashMap里以O(1)时间复杂度获取目标值。 -
还是一样注意从后向前对数组进行遍历，每次都需要记录当前元素的值和下一位较大的值。注意查找的数组是
num2中的元素。
3. 具体代码
class Solution{
//单调栈目标
public int[] nextGreaterElement(int[] nums1,int[]nums2){
int n=nums2.length;
Stack<Integer> stack=new Stack<>();
HashMap<Integer,Integer> map=new HashMap<>();
for(int i=n-1;i>=0;i--){
while(!stack.isEmpty() && nums2[i]>stack.peek()){
stack.pop();
}
int next=stack.isEmpty()?-1:stack.peek();//因为是从数组尾部遍历入栈的，因此栈顶肯定是位于当前元素之后
map.put(nums2[i],next);
stack.push(nums2[i]);
}
int[] res = new int[nums1.length];
for (int i = 0; i < nums1.length; i++) {
res[i] = map.get(nums1[i]);//借助 Map 很方便
}
return res;
}
}-
复杂度分析：
-
时间复杂度：
这段代码的时间复杂度为O(n)，其中n是nums2数组的长度。 在循环中，我们逆序遍历nums2数组，每个元素最多入栈一次，出栈一次。入栈和出栈的时间复杂度都是O(1)。同时，我们还通过HashMap构建了nums2数组中每个元素的下一个更大元素的映射关系，构建映射的时间复杂度也是O(n)。因此，整个算法的时间复杂度是O(n)。
-
空间复杂度：
这段代码的空间复杂度为O(n)，其中n是nums2数组的长度。 代码中使用了一个栈来存储元素和一个哈希表来存储下一个更大元素的映射关系。栈的最大容量取决于nums2数组的长度n，而哈希表的大小也最多是n。因此，该算法的空间复杂度是O(n)。
-
-
还有个更简单的版本：
class Solution { //《单调栈模板方法》 public int[] nextGreaterElement(int[] nums) { int[] res = new int[nums.length]; Stack<Integer> stack = new Stack<>(); for(int i = nums.length; i >= 0; i--) { //不满足单调递减，弹出直到满足了下面才入栈 while (!stack.isEmpty() && nums[i] > stack.peek()) stack.pop(); //所有元素都会得到结果 res[i] = stack.isEmpty() ? -1 : stack.peek(); //所有元素最终都会入栈 stack.push(nums[i]); } return res; } } //这个算法的复杂度只有O(n) -
单调栈的思想还是挺重要的，继续努力吧。多去练习~
