java算法day58 | 单调栈part01 ● 739. 每日温度 ● 496.下一个更大元素 I

本文主要是介绍java算法day58 | 单调栈part01 ● 739. 每日温度 ● 496.下一个更大元素 I，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

739. 每日温度

在这里插入图片描述

思路： 这道题用暴力求解法会超时。
那我们就要想如何只遍历一遍就能求解出每个位置的下一个更大值在哪呢。
主要的思想就是空间换时间。定义一个单调栈，每次遇到比栈顶元素小的或相等的，直接入栈，遇到比栈顶元素大的，while循环取栈顶元素，给这些位置计算结果。

class Solution {public int[] dailyTemperatures(int[] temperatures) {int[] res=new int[temperatures.length];Deque<Integer> stack=new LinkedList<>();stack.push(0);int index=0;for(int i=1;i<temperatures.length;i++){while(!stack.isEmpty() && temperatures[stack.peek()]<temperatures[i]){res[stack.peek()]=i-stack.pop();}stack.push(i);}while(!stack.isEmpty()){res[index++]=0;stack.pop();}return res;}
}

时间复杂度：O(n)
空间复杂度：O(n)

496.下一个更大元素 I

在这里插入图片描述

思路： 和每日温度思路一样，但需要单独开一个map，对应nums1的值和下标。

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