Day58 单调栈
739. 每日温度
我的思路:
自己只能写出超时的双重for循环遍历
看完题解,明白了栈的作用 --> 将时间复杂度优化到 O(n)
栈存储当前最大的temp[peek],等下一个更高的temp[i]出现时,弹出,并记录此时的位置peek,计算(i - peek)并存入res数组(如果弹出后,temp[i]还是比temp[peek]大,继续记录peek、保存进res、弹出)
如果temp[i]都比temp[peek]小,则一直入栈
其他情况(遍历完栈里面还有数),保持初始化值0即可
解答:
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int[] res = new int[temperatures.length];
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < temperatures.length; i++) {
while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
int idx = stack.pop();
res[idx] = i - idx;
}
stack.push(i);
}
res[temperatures.length - 1] = 0;
return res;
}
}
496.下一个更大元素 I
我的思路:
题目说明,nums1 是 nums2 的子集
类似上一题,先建立一个hashmap,存nums2的下一个更大的元素
然后遍历其子集nums1的时候,直接从hashmap中取值即可
解答:
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
Stack<Integer> stack = new Stack<>();
HashMap<Integer, Integer> hashmap = new HashMap<>();
int[] res = new int[nums1.length];
for(int num : nums2) {
hashmap.put(num, -1);
}
for(int i = 0; i < nums2.length; i++) {
while(!stack.isEmpty() && nums2[i] > nums2[stack.peek()]) {
int idx = stack.pop();
hashmap.put(nums2[idx], nums2[i]);
}
stack.push(i);
}
for(int i = 0; i < nums1.length; i++) {
res[i] = hashmap.get(nums1[i]);
}
return res;
}
}