静安集团网站建设,收费下载资源 wordpress插件,国际新闻最新消息今天新闻大事件 中方,软件开发项目报价模板一、每日温度
739. 每日温度 - 力扣#xff08;LeetCode#xff09;
从左到右除了最后一个数其他所有的数都遍历一次#xff0c;最后一个数据对应的结果肯定是 0#xff0c;就不需要计算。遍历的时候#xff0c;每个数都去向后数#xff0c;直到找到比它大的数#x…一、每日温度
739. 每日温度 - 力扣LeetCode
从左到右除了最后一个数其他所有的数都遍历一次最后一个数据对应的结果肯定是 0就不需要计算。遍历的时候每个数都去向后数直到找到比它大的数这其他数了几次就是对应的值。
public int[] dailyTemperatures(int[] T) {int length T.length;int[] result new int[length];for (int i 0; i length; i) {int current T[i];if (current 100) {for (int j i 1; j length; j) {if (T[j] current) {result[i] j - i;break;}}}}return result;
}
//单调栈方法
class Solution {public 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;} 二、下一个更大元素 I 496. 下一个更大元素 I - 力扣LeetCode 一旦要求下一个更大的元素就是用单调栈解 思路 我们可以先预处理 nums2使查询 nums1 中的每个元素在 nums2中对应位置的右边的第一个更大的元素值时不需要再遍历 nums2。于是我们将题目分解为两个子问题 第 1 个子问题如何更高效地计算 nums2中每个元素右边的第一个更大的值 第 2 个子问题如何存储第 1 个子问题的结果。 算法 使用单调栈来解决第 1 个子问题。倒序遍历 nums2并用单调栈中维护当前位置右边的更大的元素列表从栈底到栈顶的元素是单调递减的。 具体地每次我们移动到数组中一个新的位置 i就将当前单调栈中所有小于 nums2[i] 的元素弹出单调栈当前位置右边的第一个更大的元素即为栈顶元素如果栈为空则说明当前位置右边没有更大的元素。随后我们将位置 i 的元素入栈。 class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {MapInteger, Integer map new HashMapInteger, Integer();DequeInteger stack new ArrayDequeInteger();for (int i nums2.length - 1; i 0; --i) {int num nums2[i];while (!stack.isEmpty() num stack.peek()) {stack.pop();}map.put(num, stack.isEmpty() ? -1 : stack.peek());stack.push(num);}int[] res new int[nums1.length];for (int i 0; i nums1.length; i) {res[i] map.get(nums1[i]);}return res;}
}
