代码随想录算法训练营day48｜单调栈part01

第一题：739. Daily Temperatures

class Solution {// 版本 1public int[] dailyTemperatures(int[] temperatures) {int lens=temperatures.length;int []res=new int[lens];/**如果当前遍历的元素 大于栈顶元素，表示 栈顶元素的 右边的最大的元素就是 当前遍历的元素，所以弹出 栈顶元素，并记录如果栈不空的话，还要考虑新的栈顶与当前元素的大小关系否则的话，可以直接入栈。注意，单调栈里 加入的元素是 下标。*/Deque<Integer> stack=new LinkedList<>();stack.push(0);for(int i=1;i<lens;i++){if(temperatures[i]<=temperatures[stack.peek()]){stack.push(i);}else{while(!stack.isEmpty()&&temperatures[i]>temperatures[stack.peek()]){res[stack.peek()]=i-stack.peek();stack.pop();}stack.push(i);}}return  res;}//--------这 是一条分界线// 版本 2class Solution {public int[] dailyTemperatures(int[] temperatures) {int lens=temperatures.length;int []res=new int[lens];Deque<Integer> stack=new LinkedList<>();for(int i=0;i<lens;i++){while(!stack.isEmpty()&&temperatures[i]>temperatures[stack.peek()]){res[stack.peek()]=i-stack.peek();stack.pop();}stack.push(i);}return  res;}
}}

第二题：496. Next Greater Element I 

class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {Stack<Integer> temp = new Stack<>();int[] res = new int[nums1.length];Arrays.fill(res,-1);HashMap<Integer, Integer> hashMap = new HashMap<>();for (int i = 0 ; i< nums1.length ; i++){hashMap.put(nums1[i],i);}temp.add(0);for (int i = 1; i < nums2.length; i++) {if (nums2[i] <= nums2[temp.peek()]) {temp.add(i);} else {while (!temp.isEmpty() && nums2[temp.peek()] < nums2[i]) {if (hashMap.containsKey(nums2[temp.peek()])){Integer index = hashMap.get(nums2[temp.peek()]);res[index] = nums2[i];}temp.pop();}temp.add(i);}}return res;}
}// 版本2
class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {HashMap<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums1.length; i++) {map.put(nums1[i], i);}int[] res = new int[nums1.length];Stack<Integer> stack = new Stack<>();Arrays.fill(res, -1);for (int i = 0; i < nums2.length; i++) {while (!stack.isEmpty() && nums2[stack.peek()] < nums2[i]) {int pre = nums2[stack.pop()];if (map.containsKey(pre)) {res[map.get(pre)] = nums2[i];}}stack.push(i);}return res;}
}

第三题： 503. Next Greater Element II

class Solution {public int[] nextGreaterElements(int[] nums) {//边界判断if(nums == null || nums.length <= 1) {return new int[]{-1};}int size = nums.length;int[] result = new int[size];//存放结果Arrays.fill(result,-1);//默认全部初始化为-1Stack<Integer> st= new Stack<>();//栈中存放的是nums中的元素下标for(int i = 0; i < 2*size; i++) {while(!st.empty() && nums[i % size] > nums[st.peek()]) {result[st.peek()] = nums[i % size];//更新resultst.pop();//弹出栈顶}st.push(i % size);}return result;}
}