day58每日温度_下一个更大元素1

力扣739.每日温度

题目链接：https://leetcode.cn/problems/daily-temperatures/

思路

什么时候用单调栈呢？

通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。

定义一个单调栈，维护的是一个从栈顶到栈底不递减的序列。注意栈里放的是下标，判断大小时只要取出对应的数组元素即可。

有三种情况：

（1）遍历元素小于栈顶元素，此时是符合栈顶到栈底不递减的规律的，将遍历元素压入栈中；

（2）遍历元素等于栈顶元素，此时是符合栈顶到栈底不递减的规律的，将遍历元素压入栈中；

（3）重点来了：遍历元素小于栈顶元素，不符合规律了，此时用res数组记录两个下标的差值（就是第一个比自身温度高的天数了），再弹出栈顶元素，将遍历元素压入栈中。

这里只需要手动模拟一下就可以理解了。

完整代码

class Solution {public int[] dailyTemperatures(int[] temperatures) {int[] res = new int[temperatures.length];Deque<Integer> stack = new LinkedList<>();stack.push(0);for (int i = 1; i < temperatures.length; i++) {if(temperatures[i] < temperatures[stack.peek()]){stack.push(i);}else 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;}
}

力扣496.下一个更大元素1

题目链接：https://leetcode.cn/problems/next-greater-element-i/

思路

因为数组里的元素各不相同，所以用hashmap来存放元素，更容易查找。

此时栈里存放的是nums2的下标。

更多细节，需要手动模拟一下比较清楚。特别是找到遍历元素大于栈顶元素的那一段。

完整代码

class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {int[] res = new int[nums1.length];Arrays.fill(res,-1);HashMap<Integer,Integer> hashmap = new HashMap<>();for (int i = 0; i < nums1.length; i++) {hashmap.put(nums1[i],i);}Deque<Integer> stack = new LinkedList<>();stack.push(0);for (int i = 1; i < nums2.length; i++) {if(nums2[i] <= nums2[stack.peek()]){stack.push(i);}else{while (!stack.isEmpty() && nums2[i] > nums2[stack.peek()]){if(hashmap.containsKey(nums2[stack.peek()])){int index = hashmap.get(nums2[stack.peek()]);res[index] = nums2[i];}stack.pop();}stack.push(i);}}return res;}
}