【算法刷题day57】Leetcode：739. 每日温度、496.下一个更大元素 I

草稿图网站
java的Deque

Leetcode 739. 每日温度

题目：739. 每日温度
解析：代码随想录解析

解题思路

维护一个单调栈，当新元素大于栈顶，就赋予栈顶对应的res的位置i-stack.peek()。

代码

//暴力，剩一个样例无法通过
class Solution {public int[] dailyTemperatures(int[] temperatures) {int n = temperatures.length;int []res = new int[n];for (int i = 0; i < n-1; i++) {for (int p = 1; i + p < n; p++) {if (temperatures[i+p] > temperatures[i]) {res[i] = p;break;}}}return res;}
}//单调栈
class Solution {public int[] dailyTemperatures(int[] temperatures) {int n = temperatures.length;int []res = new int[n];Stack<Integer> stack = new Stack<>();for (int i = 0; i < n; i++) {while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {res[stack.peek()] = i - stack.peek();stack.pop();}stack.push(i);}return res;}
}

总结

暂无

Leetcode 496.下一个更大元素 I

题目：496.下一个更大元素 I
解析：代码随想录解析

解题思路

使用HashMap来进行值到res的索引的对应，维护一个单调栈。当HashMap中存在数的时候，将后面第一个大于的数加入res中

代码

class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums1.length; i++)map.put(nums1[i], i);int []res = new int[nums1.length];Arrays.fill(res, -1);Stack<Integer> stack = new Stack<>();for (int i = 0; i < nums2.length; i++) {while (!stack.isEmpty() && nums2[i] > nums2[stack.peek()]) {int preNum = nums2[stack.peek()];if (map.containsKey(preNum)) {res[map.get(preNum)] = nums2[i];}stack.pop();}stack.push(i);}return res;}
}

总结

暂无