代码随想录算法训练营第四十八天 | 739-每日温度、496-下一个更大元素Ⅰ、503-下一个更大元素Ⅱ
LeetCode739 每日温度
题目链接：https://leetcode.cn/problems/daily-temperatures/description/
文章讲解：https://programmercarl.com/0739.每日温度.html
视频讲解：https://www.bilibili.com/video/BV1my4y1Z7jj/?vd_source=b989f2b109eb3b17e8178154a7de7a51
通常是一维数组，要寻找任一个元素的右边或左边第一个比自己大或小的元素的位置，此时可以使用单调栈
单调栈的本质就是空间换时间，用一个栈来记录遍历过的元素，使得整个数组只需要遍历一次。栈头到栈底递增，求的是第一个更大元素；栈头到栈底递减，求的是第一个更小元素
使用单调栈主要有三个情况需要分析：
- 当前遍历的元素T[i]小于栈顶元素T[stack.peek()]
- 当前遍历的元素T[i]等于栈顶元素T[stack.peek()]
- 当前遍历的元素T[i]大于栈顶元素T[stack.peek()]
class Solution {public int[] dailyTemperatures(int[] temperatures) {Deque<Integer> stack = new LinkedList<>();int[] result = new int[temperatures.length];for(int i = 0; i < temperatures.length; i++){while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]){int index = stack.pop();result[index] = i - index;}stack.push(i);}return result;}
}
LeetCode496 下一个更大元素Ⅰ
题目链接：https://leetcode.cn/problems/next-greater-element-i/description/
文章讲解：https://programmercarl.com/0496.下一个更大元素I.html
视频讲解：https://www.bilibili.com/video/BV1jA411m7dX/?vd_source=b989f2b109eb3b17e8178154a7de7a51
首先想到的思路是，先用单调栈求出nums2中每个元素的下一个更大元素位置，然后再两层for循环对nums1和nums2进行匹配，找到nums1在nums2中对应元素，然后再检索到它的下一个更大元素
class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {Deque<Integer> stack = new LinkedList<>();int[] res = new int[nums2.length];for(int i = 0; i < nums2.length; i++){while(!stack.isEmpty() && nums2[i] > nums2[stack.peek()]){int index = stack.pop();res[index] = i - index;}stack.push(i);}int[] ans = new int[nums1.length];for(int i = 0; i < nums1.length; i++){for(int j = 0; j < nums2.length; j++){if(nums1[i] == nums2[j]){if(res[j] != 0){ans[i] = nums2[j + res[j]];}else{ans[i] = -1;}}}}return ans;}
}
进行优化，使用HashMap建立nums1的映射关系，利用映射关系找到nums1在最终答案ans数组中对应下标，填入答案
class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {Deque<Integer> stack = new LinkedList<>();HashMap<Integer, Integer> hashmap = new HashMap<>();for(int i = 0; i < nums1.length; i++){hashmap.put(nums1[i], i);}int[] ans = new int[nums1.length];Arrays.fill(ans, -1);for(int i = 0; i < nums2.length; i++){while(!stack.isEmpty() && nums2[i] > nums2[stack.peek()]){int nums2_index = stack.pop();if(hashmap.containsKey(nums2[nums2_index])){int nums1_index = hashmap.get(nums2[nums2_index]);ans[nums1_index] = nums2[i];}}stack.push(i);}return ans;}
}
LeetCode503 下一个更大元素Ⅱ
题目链接：https://leetcode.cn/problems/next-greater-element-ii/description/
文章讲解：https://programmercarl.com/0503.下一个更大元素II.html
视频讲解：https://www.bilibili.com/video/BV15y4y1o7Dw/?vd_source=b989f2b109eb3b17e8178154a7de7a51
使用取模的方式来模拟转圈过程
class Solution {public int[] nextGreaterElements(int[] nums) {Deque<Integer> stack = new LinkedList<>();int length = nums.length;int[] result = new int[length];Arrays.fill(result, -1);for(int i = 0; i < length*2; i++){while(!stack.isEmpty() && nums[i%length] > nums[stack.peek()]){int index = stack.pop();result[index] = nums[i%length];}stack.push(i%length);}return result;}
}