题目一：每日温度
题目描述：给定一个整数数组
temperatures
，表示每天的温度，返回一个数组
answer
，其中
answer[i]
是指对于第
i
天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用
0
来代替。
思路分析：
代码随想录
本题其实就是找找到一个元素右边第一个比自己大的元素，可以用单调栈解题，单调栈的本质是空间换时间，因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素，优点是只需要遍历一次。
解法：
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int lens=temperatures.length;
int []res=new int[lens];
/**
如果当前遍历的元素 大于栈顶元素，表示 栈顶元素的 右边的最大的元素就是 当前遍历的元素，
所以弹出 栈顶元素，并记录
如果栈不空的话，还要考虑新的栈顶与当前元素的大小关系
否则的话，可以直接入栈。
注意，单调栈里 加入的元素是 下标。
*/
Deque<Integer> stack=new LinkedList<>();
stack.push(0);
for(int i=1;i<lens;i++){
if(temperatures[i]<=temperatures[stack.peek()]){
stack.push(i);
}else{
while(!stack.isEmpty()&&temperatures[i]>temperatures[stack.peek()]){
res[stack.peek()]=i-stack.peek();
stack.pop();
}
stack.push(i);
}
}
return res;
}
}
题目二：下一个更大元素I
题目描述：
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]
思路分析：
代码随想录
递减栈解题，分析可能现的三种情况：
- 情况一：当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况，此时满足递增栈（栈头到栈底的顺序），所以直接入栈。
- 情况二：当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况，如果相等的话，依然直接入栈，因为我们要求的是右边第一个比自己大的元素，而不是大于等于
- 情况三：当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况，此时如果入栈就不满足递增栈了，这也是找到右边第一个比自己大的元素的时候。
解法：
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums1.length; i++) {
map.put(nums1[i], i);
}
int[] res = new int[nums1.length];
Stack<Integer> stack = new Stack<>();
Arrays.fill(res, -1);
for (int i = 0; i < nums2.length; i++) {
while (!stack.isEmpty() && nums2[stack.peek()] < nums2[i]) {
int pre = nums2[stack.pop()];
if (map.containsKey(pre)) {
res[map.get(pre)] = nums2[i];
}
}
stack.push(i);
}
return res;
}
}