Day 52 || 739. 每日温度 、 496.下一个更大元素 I 、503.下一个更大元素II
739. 每日温度
题目链接：力扣题目链接
思路：需要使用到单调栈，单调栈记录放入当前值所在数组的位置，只要当前数小于栈顶就放入，要是大于栈顶就弹出当记录的数组危及减去当前for循环的位置。
※要是求左侧或者右侧最大值栈就是从栈顶往栈底依次递增，相反左侧或者右侧最小值就是栈顶往栈底递减。
class Solution {public int[] dailyTemperatures(int[] temperatures) {Stack<Integer> stack = new Stack<>();stack.push(0);int[] res = new int[temperatures.length];for(int i=1;i<temperatures.length;i++){if(temperatures[i]<=temperatures[stack.peek()]){stack.push(i);}else{while(!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]){int prevIndex = stack.pop();res[prevIndex] = i- prevIndex;}stack.push(i);}}return res;}
}496.下一个更大元素 I
题目链接：力扣题目链接
思路：和“739. 每日温度”差不多，可以创建一个HashMap保存nums2的结果，便于nums1在其中快速找到结果。
496.下一个更大元素 I
题目链接：力扣题目链接
思路：题目关键是如何将数组循环起来，可以for循环的长度乘以二，然后利用 i%nums.length来取余用来获得当前值，其他的就都相同，结果就是新的数组从零开始取原数组的长度的值。
import java.util.Stack;
import java.util.Arrays;class Solution {public int[] nextGreaterElements(int[] nums) {Stack<Integer> stack = new Stack<>();int[] res = new int[nums.length];Arrays.fill(res, -1); // 初始化结果数组为 -1// 遍历 nums 数组两遍来模拟循环数组的效果for (int i = 0; i < nums.length * 2; i++) {int currentIndex = i % nums.length; // 当前索引，使用模运算实现循环// 当栈不为空并且栈顶元素对应的值小于当前元素while (!stack.isEmpty() && nums[stack.peek()] < nums[currentIndex]) {int prevIndex = stack.pop(); // 弹出栈顶元素的索引res[prevIndex] = nums[currentIndex]; // 更新结果数组}// 只在第一次遍历时将当前索引压入栈if (i < nums.length) {stack.push(currentIndex); // 将当前元素的索引压入栈}}return res;}
}
时间：2h