Day42 | 739. 每日温度 496.下一个更大元素 I 503.下一个更大元素II
语言
Java
739. 每日温度
每日温度
题目
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
思路
先定义一个结果数组，定义一个栈，要保证这个栈是递增的。
先放一个元素到栈中，根据给的数组长度，进行遍历，如果当前元素大于站顶元素
循环遍历直到栈为空，把栈内的元素弹出，把当前元素放入，用当前元素索引减去栈顶索引，获得结果加入到结果数组中。
如果小于栈顶元素，之间把当前元素加到栈中。
最后返回结果数组。
代码
class Solution {public int[] dailyTemperatures(int[] temperatures) {int len = temperatures.length;int[] res = new int[len];Deque<Integer> stack = new LinkedList<>();stack.push(0);for (int i = 1; i < len; 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;}
}易错点
把三种情况捋清楚
当前元素大于栈顶元素
当前元素小于等于栈顶元素
496.下一个更大元素 I
下一个更大元素 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] 是如上所述的 下一个更大元素 。
思路
本题也是单调栈的题，与上一道题类似，先定义一个栈，一个结果数组
把结果数组中填满-1；将数组一中的索引和数值用Map存起来。
添加一个元素到栈中，循环比较当前元素和栈顶元素的大小
如果当前元素大，循环比较，找离的近的比他大的元素，添加到结果集中，并将元素弹出
将当前元素加入栈中。
如果当前元素小，直接加入栈中。
返回结果数组。
代码
class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {Stack<Integer> temp = new Stack<>();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);} temp.add(0);for (int i = 1; i < nums2.length; i++) {if (nums2[i] <= nums2[temp.peek()]) {temp.add(i);} else {while (!temp.isEmpty() && nums2[temp.peek()] < nums2[i]) {if (hashMap.containsKey(nums2[temp.peek()])){Integer index = hashMap.get(nums2[temp.peek()]);res[index] = nums2[i];}temp.pop();}temp.add(i);}}return res;}
}易错点
将整个数组赋值为-1
也是注意三种条件的判断。
503.下一个更大元素II
下一个更大元素II
题目
给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
思路
本题与前两道题十分相似，不同在于需要进行循环搜索
用一个取模就可以解决，具体细节看代码
代码
class Solution {public int[] nextGreaterElements(int[] nums) {//边界判断if(nums == null || nums.length <= 1) {return new int[]{-1};}int size = nums.length;int[] result = new int[size];//存放结果Arrays.fill(result,-1);//默认全部初始化为-1Stack<Integer> st= new Stack<>();//栈中存放的是nums中的元素下标for(int i = 0; i < 2*size; i++) {while(!st.empty() && nums[i % size] > nums[st.peek()]) {result[st.peek()] = nums[i % size];//更新resultst.pop();//弹出栈顶}st.push(i % size);}return result;}
}易错点
取模来达到循环的效果
总结
今天开启了单调栈，做起来有点懵懵的。
等过几天回来再好好刷几遍。
继续加油！