代码随想录算法训练营day58

2023-06-11 17:26| 来源: 网络整理| 查看: 265

代码随想录算法训练营day58 | 739. 每日温度，496.下一个更大元素 I 739. 每日温度解法一：单调栈（视频版）解法二：单调栈（自己写的，反向遍历） 496.下一个更大元素 I解法一：单调栈（自己写的，复杂）解法二：单调栈（视频教程版）总结

739. 每日温度

教程视频：https://www.bilibili.com/video/BV1my4y1Z7jj 在这里插入图片描述

解法一：单调栈（视频版）

遍历时将已经遍历的元素，存入栈中，期间保持栈顶到栈底为递增的。

class Solution { public int[] dailyTemperatures(int[] temperatures) { int[] answer = new int[temperatures.length]; Deque stack=new LinkedList(); stack.push(0); for(int i=1;i stack.push(i); }else{ while(!stack.isEmpty() && temperatures[i]>temperatures[stack.peek()]){ answer[stack.peek()]=i-stack.peek(); stack.pop(); } stack.push(i); } } return answer; } } 解法二：单调栈（自己写的，反向遍历） class Solution { public int[] dailyTemperatures(int[] temperatures) { int[] answer = new int[temperatures.length]; // Stack stack = new Stack(); Deque stack=new LinkedList(); for(int i=temperatures.length-1;i>=0;i--){ while(!stack.isEmpty() && temperatures[i]>=temperatures[stack.peek()]){ stack.pop(); } if(stack.isEmpty()){ answer[i]=0; }else{ answer[i] = stack.peek()-i; } stack.push(i); } return answer; } } 496.下一个更大元素 I

教程视频：https://www.bilibili.com/video/BV1jA411m7dX 在这里插入图片描述

解法一：单调栈（自己写的，复杂） class Solution { public int[] nextGreaterElement(int[] nums1, int[] nums2) { Deque stack = new LinkedList(); int[] result = new int[nums2.length]; stack.push(0); for(int i=1;i stack.push(i); }else{ while(!stack.isEmpty() && nums2[i]>nums2[stack.peek()]){ result[stack.peek()]=i-stack.peek(); stack.pop(); } stack.push(i); } } // while(!stack.isEmpty()){ // result[stack.pop()]=-1; // } for(int j=0;j for(int j=0;j if(result[j]==0){ result2[i]=-1; }else{ result2[i]=nums2[j+result[j]]; } } } } return result2; } } 解法二：单调栈（视频教程版） class Solution { public int[] nextGreaterElement(int[] nums1, int[] nums2) { Stack temp = new Stack(); int[] res = new int[nums1.length]; Arrays.fill(res,-1); HashMap hashMap = new HashMap(); for (int i = 0 ; i if (nums2[i] while (!temp.isEmpty() && nums2[temp.peek()] Integer index = hashMap.get(nums2[temp.peek()]); res[index] = nums2[i]; } temp.pop(); } temp.add(i); } } return res; } } 总结

1、单调栈存放的是数组下标，这样可以更方便的查询元素并获取距离。

【本文地址】

公司简介

联系我们