无锡网站优化哪家快,网站怎么做数据备份,wordpress和ucenter,迅 网站 模板739. 每日温度
给定一个整数数组 temperatures #xff0c;表示每天的温度#xff0c;返回一个数组 answer #xff0c;其中 answer[i] 是指对于第 i 天#xff0c;下一个更高温度出现在几天后。如果气温在这之后都不会升高#xff0c;请在该位置用 0 来代替。
示例 1: …739. 每日温度
给定一个整数数组 temperatures 表示每天的温度返回一个数组 answer 其中 answer[i] 是指对于第 i 天下一个更高温度出现在几天后。如果气温在这之后都不会升高请在该位置用 0 来代替。
示例 1:
输入: temperatures [73,74,75,71,69,72,76,73] 输出: [1,1,4,2,1,1,0,0] 示例 2:
输入: temperatures [30,40,50,60] 输出: [1,1,1,0] 示例 3:
输入: temperatures [30,60,90] 输出: [1,1,0]
方法一
class Solution {// 版本 1public int[] dailyTemperatures(int[] temperatures) {int lenstemperatures.length;int []resnew int[lens];/**如果当前遍历的元素 大于栈顶元素表示 栈顶元素的 右边的最大的元素就是 当前遍历的元素所以弹出 栈顶元素并记录如果栈不空的话还要考虑新的栈顶与当前元素的大小关系否则的话可以直接入栈。注意单调栈里 加入的元素是 下标。*/DequeInteger stacknew LinkedList();stack.push(0);for(int i1;ilens;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;}这段代码是用于解决「每日温度」问题的Java实现这个问题的目标是给定一个整数数组 temperatures其中每个元素表示每天的温度返回一个新的数组其中每个元素表示直到未来几天才会出现更高的温度的天数。如果不存在未来几天会出现更高的温度那么该位置的值为0。
代码解析 初始化: 创建一个与 temperatures 长度相同的数组 res用于存放结果。使用一个单调栈 stack数据结构为 Deque在Java中通常使用 LinkedList 实现用于存储下标。 遍历并维护单调栈: 遍历 temperatures 数组中的每个元素。对于当前遍历到的元素 temperatures[i] 如果该元素小于等于栈顶元素对应的温度即 temperatures[i] temperatures[stack.peek()]则将当前下标 i 入栈。否则进入一个while循环 当栈不为空且当前元素大于栈顶元素对应的温度时弹出栈顶元素并计算栈顶元素下标到当前下标 i 的距离即 i - stack.peek()并将这个距离存入结果数组 res 的对应位置。继续循环直到栈为空或当前元素不大于栈顶元素对应的温度。 最后将当前下标 i 入栈。 返回结果: 返回结果数组 res其中每个元素表示直到未来几天才会出现更高的温度的天数。
时间复杂度和空间复杂度
时间复杂度: O(n)其中 n 是数组 temperatures 的长度。每个元素至多被放入和弹出栈一次。空间复杂度: O(n)需要一个大小为 n 的结果数组 res 和一个单调栈 stack。
总结
这段代码通过使用单调栈的策略有效地解决了每日温度问题能够快速找到每个温度元素右边第一个比它大的温度元素的位置。单调栈是一种常用的数据结构在处理与单调性相关的数组或序列问题时非常有用例如寻找最近的更大或更小的元素、股票价格波动分析等。在实际应用中掌握单调栈的原理和使用方法能够帮助解决一系列经典问题提高代码效率。
方法二 //--------这 是一条分界线// 版本 2class Solution {public int[] dailyTemperatures(int[] temperatures) {int lenstemperatures.length;int []resnew int[lens];DequeInteger stacknew LinkedList();for(int i0;ilens;i){while(!stack.isEmpty()temperatures[i]temperatures[stack.peek()]){res[stack.peek()]i-stack.peek();stack.pop();}stack.push(i);}return res;}这段代码同样是用于解决「每日温度」问题的Java实现其目标与前一版本相同即给定一个整数数组 temperatures返回一个新的数组其中每个元素表示直到未来几天才会出现更高的温度的天数。如果不存在未来几天会出现更高的温度那么该位置的值为0。
代码解析 初始化: 创建一个与 temperatures 长度相同的数组 res用于存放结果。使用一个单调栈 stack数据结构为 Deque在Java中通常使用 LinkedList 实现用于存储下标。 遍历并维护单调栈: 遍历 temperatures 数组中的每个元素。对于当前遍历到的元素 temperatures[i] 进入一个while循环只要栈不为空且当前元素大于栈顶元素对应的温度执行以下操作 计算栈顶元素下标到当前下标 i 的距离即 i - stack.peek()并将这个距离存入结果数组 res 的对应位置。弹出栈顶元素。 将当前下标 i 入栈。 返回结果: 返回结果数组 res其中每个元素表示直到未来几天才会出现更高的温度的天数。
时间复杂度和空间复杂度
时间复杂度: O(n)其中 n 是数组 temperatures 的长度。每个元素至多被放入和弹出栈一次。空间复杂度: O(n)需要一个大小为 n 的结果数组 res 和一个单调栈 stack。
版本对比
相比于版本1版本2的代码在遍历过程中直接从头开始简化了代码逻辑将入栈操作放在了while循环的外部。这种写法同样有效且逻辑上更清晰因为它避免了不必要的条件判断如版本1中的 temperatures[i] temperatures[stack.peek()]。每次遍历到新元素时代码首先处理栈中所有比当前元素小的元素然后将当前元素入栈这一过程确保了栈内的元素始终按温度递减的顺序排列即形成了一个单调递减栈。
总结
通过使用单调栈的策略版本2的代码同样有效地解决了每日温度问题。这种实现方式不仅保持了良好的时间复杂度和空间复杂度而且在代码结构上更为精简和直观有助于提高代码的可读性和维护性。单调栈在处理与单调性相关的数组或序列问题时是一种非常有用的工具熟练掌握其使用方法对于解决一系列经典问题具有重要意义。
496. 下一个更大元素 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
输入nums1 [4,1,2], nums2 [1,3,4,2]. 输出[-1,3,-1] 解释nums1 中每个值的下一个更大元素如下所述
4 用加粗斜体标识nums2 [1,3,4,2]。不存在下一个更大元素所以答案是 -1 。1 用加粗斜体标识nums2 [1,3,4,2]。下一个更大元素是 3 。2 用加粗斜体标识nums2 [1,3,4,2]。不存在下一个更大元素所以答案是 -1 。 示例 2
输入nums1 [2,4], nums2 [1,2,3,4]. 输出[3,-1] 解释nums1 中每个值的下一个更大元素如下所述
2 用加粗斜体标识nums2 [1,2,3,4]。下一个更大元素是 3 。4 用加粗斜体标识nums2 [1,2,3,4]。不存在下一个更大元素所以答案是 -1 。
方法一
class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {StackInteger temp new Stack();int[] res new int[nums1.length];Arrays.fill(res,-1);HashMapInteger, 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;}
}这段代码是用于解决「下一个更大元素 I」问题的Java实现。给定两个没有重复元素的数组 nums1 和 nums2其中 nums1 是 nums2 的一个子集目标是对于 nums1 中的每一个元素找到在 nums2 中下一个更大的元素的值。如果没有这样的元素那么输出 -1。
代码解析 初始化: 创建一个单调栈 temp数据结构为 Stack用于存储 nums2 中元素的下标。创建一个结果数组 res初始化所有元素为 -1长度与 nums1 相同。创建一个哈希映射 hashMap用于存储 nums1 中元素及其在 res 数组中的下标以便快速查找和更新结果。 遍历并维护单调栈: 遍历 nums2 数组中的每个元素。对于当前遍历到的元素 nums2[i] 如果该元素小于等于栈顶元素对应的值即 nums2[i] nums2[temp.peek()]则将当前下标 i 入栈。否则进入一个while循环 当栈不为空且当前元素大于栈顶元素对应的值时检查栈顶元素是否在 nums1 中如果是则获取该元素在 res 中的下标并将当前元素的值赋给 res 的对应位置。继续循环直到栈为空或当前元素不大于栈顶元素对应的值。 最后将当前下标 i 入栈。 返回结果: 返回结果数组 res其中每个元素表示 nums1 中对应元素在 nums2 中的下一个更大元素的值若不存在则为 -1。
时间复杂度和空间复杂度
时间复杂度: O(m n)其中 m 和 n 分别是数组 nums1 和 nums2 的长度。每个元素至多被放入和弹出栈一次哈希表的查找操作平均时间复杂度为 O(1)。空间复杂度: O(n)需要一个大小为 n 的单调栈 temp 和一个哈希映射 hashMap以及一个结果数组 res。
总结
这段代码通过使用单调栈和哈希映射的策略有效地解决了下一个更大元素问题能够快速找到 nums1 中每个元素在 nums2 中下一个更大元素的值。单调栈是一种常用的数据结构在处理与单调性相关的数组或序列问题时非常有用结合哈希映射能够进一步提高查找效率。在实际应用中掌握这些数据结构和算法原理能够帮助解决一系列经典问题提高代码效率和性能。
方法二
// 版本2
class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {HashMapInteger, Integer map new HashMap();for (int i 0; i nums1.length; i) {map.put(nums1[i], i);}int[] res new int[nums1.length];StackInteger stack new Stack();Arrays.fill(res, -1);for (int i 0; i nums2.length; i) {while (!stack.isEmpty() nums2[stack.peek()] nums2[i]) {int pre nums2[stack.pop()];if (map.containsKey(pre)) {res[map.get(pre)] nums2[i];}}stack.push(i);}return res;}
}这段代码是用于解决「下一个更大元素 I」问题的另一种Java实现其实现思路与之前解析的版本相似但代码结构和变量命名有所不同旨在解决给定两个没有重复元素的数组 nums1 和 nums2其中 nums1 是 nums2 的一个子集对于 nums1 中的每一个元素找到在 nums2 中下一个更大的元素的值。如果没有这样的元素那么输出 -1。
代码解析 初始化: 创建一个哈希映射 map用于存储 nums1 中元素及其在 nums1 中的下标以便快速查找和更新结果。创建一个结果数组 res初始化所有元素为 -1长度与 nums1 相同。创建一个单调栈 stack数据结构为 Stack用于存储 nums2 中元素的下标。 构建哈希映射: 遍历 nums1 数组将每个元素及其在 nums1 中的下标存储在 map 中。 遍历并维护单调栈: 遍历 nums2 数组中的每个元素。对于当前遍历到的元素 nums2[i] 如果栈不为空并且栈顶元素对应的值小于当前元素即 nums2[stack.peek()] nums2[i]则 弹出栈顶元素并获取其值。如果弹出的元素在 nums1 中即 map 中存在该元素那么在 res 数组的对应位置填入当前元素的值。 继续这个过程直到栈为空或者栈顶元素对应的值不再小于当前元素。最后将当前下标 i 入栈。 返回结果: 返回结果数组 res其中每个元素表示 nums1 中对应元素在 nums2 中的下一个更大元素的值若不存在则为 -1。
时间复杂度和空间复杂度
时间复杂度: O(m n)其中 m 和 n 分别是数组 nums1 和 nums2 的长度。每个元素至多被放入和弹出栈一次哈希表的查找操作平均时间复杂度为 O(1)。空间复杂度: O(n)需要一个大小为 n 的单调栈 stack 和一个哈希映射 map以及一个结果数组 res。
总结
这段代码同样通过使用单调栈和哈希映射的策略有效地解决了下一个更大元素问题能够快速找到 nums1 中每个元素在 nums2 中下一个更大元素的值。代码结构清晰逻辑直观是解决这类问题的一种典型且高效的方法。掌握这些数据结构和算法原理能够帮助解决一系列经典问题提高代码效率和性能。在实际应用中根据具体需求和场景选择合适的数据结构和算法是非常重要的。
503. 下一个更大元素 II
给定一个循环数组 nums nums[nums.length - 1] 的下一个元素是 nums[0] 返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序这个数字之后的第一个比它更大的数这意味着你应该循环地搜索它的下一个更大的数。如果不存在则输出 -1 。
示例 1:
输入: nums [1,2,1] 输出: [2,-1,2] 解释: 第一个 1 的下一个更大的数是 2 数字 2 找不到下一个更大的数 第二个 1 的下一个最大的数需要循环搜索结果也是 2。 示例 2:
输入: nums [1,2,3,4,3] 输出: [2,3,4,-1,4]
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);//默认全部初始化为-1StackInteger 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;}
}这段代码是用于解决「下一个更大元素 II」问题的Java实现。给定一个循环数组 nums数组中元素的下一个元素是数组的第一个元素目标是返回一个数组其中每个元素是原数组中下一个更大元素的值如果没有更大的元素则对应位置的值为 -1。
代码解析 初始化: 创建一个单调栈 st数据结构为 Stack用于存储 nums 中元素的下标。创建一个结果数组 result初始化所有元素为 -1长度与 nums 相同。 遍历并维护单调栈: 遍历 nums 数组两次即遍历 2 * nums 的长度考虑到循环数组的性质使用模运算 i % size 来获取实际数组下标。对于当前遍历到的元素 nums[i % size] 如果栈不为空并且栈顶元素对应的值小于当前元素即 nums[st.peek()] nums[i % size]则 更新 result 数组中对应位置的值为当前元素的值。弹出栈顶元素。 继续这个过程直到栈为空或者栈顶元素对应的值不再小于当前元素。最后将当前下标 i % size 入栈。 返回结果: 返回结果数组 result其中每个元素表示原数组 nums 中对应元素的下一个更大元素的值若不存在则为 -1。
时间复杂度和空间复杂度
时间复杂度: O(n)其中 n 是数组 nums 的长度。虽然代码中遍历了 2 * nums 的长度但是每个元素至多被放入和弹出栈一次因此总的时间复杂度为 O(n)。空间复杂度: O(n)需要一个大小为 n 的单调栈 st 和一个结果数组 result。
总结
这段代码通过使用单调栈的策略有效地解决了下一个更大元素 II 问题能够处理循环数组并找到每个元素的下一个更大元素的值。代码逻辑清晰通过两次遍历数组并使用模运算处理循环数组的特点实现了高效的解题策略。单调栈在处理这类问题时表现出了强大的能力能够快速找到特定条件下下一个更大的元素是解决此类问题的经典方法。在实际应用中了解和掌握单调栈的使用方法对于解决与单调性相关的数组或序列问题具有重要意义。
