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;}
}