单调栈专门解决Next Greater Number，这句点题

739. 每日温度

暴力超时

class Solution {public int[] dailyTemperatures(int[] temperatures) {//双指针解法int slow=0;int fast=1;while(fast<temperatures.length){if(temperatures[fast]<=temperatures[slow]){fast++;}else{temperatures[slow]=fast-slow;slow++;fast=slow+1;}if(fast==temperatures.length-1&&fast-slow!=1){temperatures[slow]=0;slow++;fast=slow+1;}//处理倒数第2个if(fast==temperatures.length-1&&fast-slow==1&&temperatures[fast]<=temperatures[slow]){slow--;temperatures[slow]=0;}}//    System.out.println(slow);temperatures[temperatures.length-1]=0;return temperatures;}
}

单调栈写法

单调栈中存放的是元素的下标，单调栈从栈头(开口处)到栈底是递增的

使用单调栈主要有三个判断条件。

• 当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
• 当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
• 当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况

代码实现

class Solution {public int[] dailyTemperatures(int[] temperatures) {int[] res=new int[temperatures.length];Deque<Integer> stack=new LinkedList<>();stack.push(0);//记住单调栈存放的是元素的下标for(int i=1;i<temperatures.length;i++){if(temperatures[i]<=temperatures[stack.peek()]){//当前遍历的元素小于等于栈顶元素，直接把下标入栈stack.push(i);}else{while(!stack.isEmpty()&&temperatures[i]>temperatures[stack.peek()]){//一定要加上后面这个大于的判断，因为如果!stack.isEmpty()但可能有temperatures[i]<=temperatures[stack.peek()]的情况res[stack.peek()]=i-stack.peek();stack.pop();}stack.push(i);}}return res;}
}

496.下一个更大元素 I

 重点没有重复元素 的数组 nums1 和 nums2

这道题的解法有点绕啊

首先对nums1：把元素和其对应的下标存放到map中

其次遍历nums2数组：注意栈存放的是nums2元素的下标，是下标！

如果当前元素小于等于栈顶下标对应的元素，说明当前元素不是要寻找的第一个更大，直接将其下标入栈；

如果当前元素大于栈顶下标对应的元素，说明就是在nums2中找到了第一个更大的，这时对栈进行非空判断，如果当前nums2栈顶元素也在map中出现的话，说明是nums1需要的，我们找到这个元素在nums1的下标位置index，这时候把当前遍历下标对应的元素值 赋值给index

上面有点绕，总而言之，就是在nums2中寻找nums1中元素的右边最大，需要纸笔画一下清楚。

代码实现 

class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {int[] res=new int[nums1.length];Stack<Integer> stack = new Stack<>();//用来遍历的nums2下标Arrays.fill(res,-1);HashMap<Integer,Integer> hashMap=new HashMap<>();for(int i=0;i<nums1.length;i++){hashMap.put(nums1[i],i);}stack.push(0);for(int i=1;i<nums2.length;i++){if(nums2[i]<=nums2[stack.peek()]){//当前元素小于等于栈顶元素也依然入栈stack.push(i);//存放的是下标，下标是递增的}else{//当前下标元素大于栈顶下标元素while(!stack.isEmpty()&&nums2[stack.peek()]<nums2[i]){if(hashMap.containsKey(nums2[stack.peek()])){Integer index=hashMap.get(nums2[stack.peek()]);res[index]=nums2[i];}stack.pop();}stack.push(i);}}return res;}
}