代码随想录算法训练营第五十八天 | 739. 每日温度、 496.下一个更大元素 I
739. 每日温度
情况一：当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
此时满足递增栈（栈头到栈底的顺序），所以直接入栈。
情况二：当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
如果相等的话，依然直接入栈，因为我们要求的是右边第一个比自己大的元素，而不是大于等于！
情况三：当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况
此时如果入栈就不满足递增栈了，这也是找到右边第一个比自己大的元素的时候
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int[] answer = new int[temperatures.length];
// 单调栈，保持栈中的元素为单调递减
// 单调栈装的是元素的索引位置
LinkedList<Integer> stack = new LinkedList<>();
for(int i = 0; i < answer.length; ++i) {
// 判断当前元素与栈顶元素大小
while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peekLast()]) {
// 若大于栈顶元素，pop栈顶元素且set栈顶元素对应位置到当前元素位置的距离
int pre = stack.pollLast();
answer[pre] = i - pre;
}
// 不大于，直接将元素索引添加至栈顶
stack.addLast(i);
}
return answer;
}
}
496.下一个更大元素 I
题目链接：496. 下一个更大元素 I - 力扣（LeetCode）
此题就是在739. 每日温度 - 力扣（LeetCode）基础上，多增加了一个nums1作为nums2的子序列
我们依旧使用单调栈来保存nums2中的元素，然后使用map保存nums1的元素，在遍历nums2中元素的同时查找map，看看是否存在
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int len1 = nums1.length;
int len2 = nums2.length;
int[] ans = new int[len1];
//默认为找不到，所有都为-1
Arrays.fill(ans, -1);
Map<Integer, Integer> dic = new HashMap<>();
// map保存nums1中每个元素的索引位置
for(int i = 0; i < len1; ++i) {
dic.put(nums1[i], i);
}
Deque<Integer> stack = new ArrayDeque<>();
for(int i = 0; i < len2; ++i) {
// 判断当前元素与栈顶元素大小
while(!stack.isEmpty() && nums2[stack.peekLast()] < nums2[i]) {
// 满足情况三，需要pop栈顶元素直到满足情况一或二
int top = nums2[stack.pollLast()];
// 判断栈顶元素是否存在于nums1中
if(dic.containsKey(top)) {
// 若存在，更新nums1元素对应的ans[]
ans[dic.get(top)] = nums2[i];
}
}
stack.offerLast(i);
}
return ans;
}
}
总结
使用单调栈主要有三个判断条件。
- 当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
- 当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
- 当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况
