739. 每日温度 - 力扣LeetCode请根据每日 气温 列表重新生成一个列表。对应位置的输出为要想观测到更高的气温至少需要等待的天数。如果气温在这之后都不会升高请在该位置用 0 来代替。例如给定一个列表 temperatures [73, 74, 75, 71, 69, 72, 76, 73]你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。提示气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度都是在 [30, 100] 范围内的整数。public int[] dailyTemperatures(int[] temperatures) { int[] result new int[temperatures.length]; DequeInteger deque new ArrayDeque(); deque.push(0); for (int i 1; i temperatures.length; i) { // 与栈顶元素相比更小 if (temperatures[i] temperatures[deque.peek()]) { deque.push(i); } // 栈顶元素比当前元素大 else { while (!deque.isEmpty() temperatures[i] temperatures[deque.peek()]) { int index deque.pop(); result[index] i - index; } deque.push(i); } } return result; }解题暴力如果对每一天都向后遍历寻找第一个更高温度时间复杂度为 O(N2)O(N2) 在数据量较大时会超时。我们需要一种方法能够以 O(N)O(N) 的时间复杂度解决这个问题。为此我们需要用到单调栈。我们要找的是“下一个更大元素”。当我们遍历到一个新温度时它可能是前面某些“等待中”的低温天的答案。如果我们维护一个栈栈中存储的是尚未找到更高温度的日期索引。为了保证效率我们让栈中的温度保持单调递减。如果当前温度比栈顶温度低或相等说明还没找到答案直接入栈等待。如果当前温度比栈顶温度高说明当前这一天就是栈顶那一天的“下一个更高温度”。此时可以弹出栈顶计算天数差并继续检查新的栈顶直到栈顶温度不再低于当前温度或栈为空。算法步骤初始化结果数组result长度与输入相同默认值为 0。创建一个栈stack用于存储日期的索引而不是温度值因为我们需要计算天数差i - index。遍历温度数组temperatures设当前索引为i循环判断当栈不为空且当前温度temperatures[i]大于栈顶索引对应的温度temperatures[stack.peek()]时弹出栈顶索引index stack.pop()。计算等待天数result[index] i - index。重复此过程直到栈为空或当前温度不再高于栈顶温度。入栈将当前索引i压入栈中因为它还没找到自己的下一个更高温度或者它成为了新的栈底/中间元素。遍历结束后栈中剩余的索引表示那些之后没有更高温度的日子它们的result值保持默认的 0 即可。关键我们是存下标而不是值因为我们要计算下标差而不是值差。同时我们需要保证栈是单调递增的496. 下一个更大元素 I - 力扣LeetCode给你两个 没有重复元素 的数组 nums1 和 nums2 其中nums1 是 nums2 的子集。请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在对应位置输出 -1 。示例 1:输入: nums1 [4,1,2], nums2 [1,3,4,2].输出: [-1,3,-1]解释:对于 num1 中的数字 4 你无法在第二个数组中找到下一个更大的数字因此输出 -1 。对于 num1 中的数字 1 第二个数组中数字1右边的下一个较大数字是 3 。对于 num1 中的数字 2 第二个数组中没有下一个更大的数字因此输出 -1 。示例 2:输入: nums1 [2,4], nums2 [1,2,3,4].输出: [3,-1]解释:对于 num1 中的数字 2 第二个数组中的下一个较大数字是 3 。对于 num1 中的数字 4 第二个数组中没有下一个更大的数字因此输出-1 。提示1 nums1.length nums2.length 10000 nums1[i], nums2[i] 10^4nums1和nums2中所有整数 互不相同nums1 中的所有整数同样出现在 nums2 中public int[] nextGreaterElement(int[] nums1, int[] nums2) { if (nums1.length 0) { return new int[0]; } int[] result new int[nums1.length]; Arrays.fill(result, -1); DequeInteger deque new ArrayDeque(); HashMapInteger, Integer map new HashMap(); for (int i 0; i nums1.length; i) { map.put(nums1[i], i); } deque.push(0); for (int i 1; i nums2.length; i) { if (nums2[i] nums2[deque.peek()]) { deque.push(i); } else { while (!deque.isEmpty() nums2[i] nums2[deque.peek()]) { if (map.containsKey(nums2[deque.peek()])) { int value map.get(nums2[deque.peek()]); result[value] nums2[i]; } deque.pop(); } deque.push(i); } } return result; }解题本题也是需要用到单调栈同时我们还要考虑俩个数组的映射关系所以还用到了哈希表算法步骤建立索引映射创建一个哈希表map存储nums1中每个数值及其在nums1中的下标。目的当我们在nums2中找到某个数的“下一个更大值”时能迅速知道这个结果应该填在result数组的哪个位置。初始化结果数组创建result数组长度与nums1相同。将所有值初始化为-1默认找不到更大值。遍历nums2并维护单调栈使用栈deque存储nums2的索引注意存索引是为了方便获取数值nums2[index]。遍历nums2的每个元素nums2[i]循环判断当栈不为空且当前元素nums2[i]大于栈顶索引对应的元素nums2[stack.peek()]时说明nums2[i]就是栈顶元素的“下一个更大元素”。获取栈顶元素的值val nums2[stack.peek()]。关键检查检查val是否存在于map中即它是否属于nums1。如果存在通过map找到它在nums1中的下标idx并将result[idx]更新为nums2[i]。弹出栈顶元素 (pop)。入栈将当前索引i压入栈中。返回结果遍历结束后result中仍为-1的位置表示未找到更大元素符合题意503. 下一个更大元素 II - 力扣LeetCode给定一个循环数组最后一个元素的下一个元素是数组的第一个元素输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序这个数字之后的第一个比它更大的数这意味着你应该循环地搜索它的下一个更大的数。如果不存在则输出 -1。示例 1:输入: [1,2,1]输出: [2,-1,2]解释: 第一个 1 的下一个更大的数是 2数字 2 找不到下一个更大的数第二个 1 的下一个最大的数需要循环搜索结果也是 2。提示:1 nums.length 10^4-10^9 nums[i] 10^9public int[] nextGreaterElements(int[] nums) { int[] result new int[nums.length]; Arrays.fill(result, -1); DequeInteger deque new ArrayDeque(); deque.push(0); for (int i 1; i nums.length * 2; i) { int index i % nums.length; if (nums[index] nums[deque.peek()]) { deque.push(index); } else { while (!deque.isEmpty() nums[index] nums[deque.peek()]) { result[deque.peek()] nums[index]; deque.pop(); } deque.push(index); } } return result; }解题遇到循环的时候通常可以加俩份相同部分拼接起来这样就可以包含到循环部分。更好的方法是使用下标取模因为前者会更加消耗空间后者只需要循环的时候值为2倍即可。策略一数组拼接直观但耗空间将原数组复制一份拼接到后面变成[1, 2, 1, 1, 2, 1]然后在这个新数组上运行标准的“下一个更大元素”算法。缺点需要 O(2N)O(2N) 的额外空间。策略二取模运算你的代码采用的方法最优不实际创建新数组而是通过遍历两次原数组的长度并利用i % n来获取对应的索引。遍历范围从0到2 * n - 1。真实索引index i % n。逻辑第一次遍历0到n-1处理普通情况。第二次遍历n到2n-1相当于处理“绕回”到数组头部的情况为那些在第一次遍历中没找到答案的元素通常是较大的数或末尾的数提供机会。算法步骤初始化创建result数组长度与nums相同全部填充-1。创建单调栈deque存储索引。先将索引0入栈。模拟循环遍历循环变量i从1到2 * nums.length - 1。计算当前真实索引index i % nums.length。单调栈逻辑当栈不为空且nums[index]大于栈顶索引对应的值nums[stack.peek()]时说明找到了栈顶元素的下一个更大值。更新结果result[stack.peek()] nums[index]。弹出栈顶。将当前index入栈。注意在第二次遍历中我们主要是在“消费”栈里剩下的元素。虽然代码中也会把第二次的index再次入栈但这不影响结果因为遍历结束后我们就返回了不会再处理这些新入栈的元素。返回结果。