代码随想录算法训练营第四十五天-739每日温度、496下一个更大元素 I、503下一个更大元素II

前言
状态：739 看解析。496 看解析。503 根据 739 写出。
更新

1	24-07-11 初始记录

初步题解

public static int[] nextGreaterElements(int[] nums) {  
    int[] result = new int[nums.length];  
    Arrays.fill(result, -1);  
  
    Stack<Integer> stack = new Stack<>();  
    stack.push(0);  
  
    for (int i = 0; i < nums.length * 2; i++) {  
        while (!stack.isEmpty() && nums[i % nums.length] > nums[stack.peek()]) {  
            result[stack.peek()] = nums[i % nums.length];  
            stack.pop();  
        }  
        stack.push(i % nums.length);  
    }  
  
    return result;  
}

看解析

739 每日温度

解析：(https://programmercarl.com/0739.每日温度.html)

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

public static int[] dailyTemperatures(int[] temperatures) {  
    Deque<Integer> stack = new LinkedList<>();  
    int[] result = new int[temperatures.length];  
  
    stack.push(0);  
    for (int i = 1; i < temperatures.length; i++) {
	    // 当前元素小于等于栈顶元素，直接继续放入  
        if (temperatures[i] <= temperatures[stack.peek()]) {  
            stack.push(i);  
        // 当前元素大于栈顶元素，弹出元素，计算result，（直到当前元素不大于栈顶元素），将当前元素加入栈
        } else {  
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {  
                result[stack.peek()] = i - stack.peek();  
                stack.pop();  
            }  
            stack.push(i);  
        }  
    }  
    return result;  
}

// 简化版本
public int[] dailyTemperatures(int[] temperatures) {  
    Deque<Integer> stack = new LinkedList<>();  
    int[] result = new int[temperatures.length];  
  
    stack.push(0);  
    for (int i = 1; i < temperatures.length; i++) {
	    while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {  
                result[stack.peek()] = i - stack.peek();  
                stack.pop();  
            }  
        stack.push(i);    
    }  
    return result;  
}

496 下一个更大元素 I

解析：(https://programmercarl.com/0496.下一个更大元素I.html)

public int[] nextGreaterElement(int[] nums1, int[] nums2) {  
    int[] result = new int[nums1.length];  
    Stack<Integer> stack = new Stack<>();  
  
    Arrays.fill(result, -1);  
  
    HashMap<Integer, Integer> map = new HashMap<>();  
    for (int i = 0; i < nums1.length; i++) {  
        map.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[i] > nums2[stack.peek()]) {  
                // num1中包含整这个元素  
                if (map.containsKey(nums2[stack.peek()])) {  
                    // result中的对应下标为这个元素的后一位  
                    result[map.get(nums2[stack.peek()])] = nums2[i];  
                }  
                stack.pop();  
            }  
            stack.push(i);  
        }  
    }  
    return result;  
}

503 下一个更大元素 II

解析：(https://programmercarl.com/0503.下一个更大元素II.html)