代码随想录算法训练营 | 739. 每日温度，496.下一个更大元素 I ，503.下一个更大元素II

739. 每日温度
题目链接：739. 每日温度
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰每日温度
日期：2024-10-20

想法：遍历一遍数组，用栈来存数组下标做记录，因为要找更高得温度，当当前遍历的温度大于栈头存储（存的下标）的温度时，就可以知道栈头要过多少天遇到高温，低的时候直接入栈。
Java代码如下：

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int len = temperatures.length;
        int[] res = new int[len];
        Deque<Integer> st = new LinkedList<>();
        st.push(0);

        for(int i = 1; i < len; i++) {
            if(temperatures[i] <= temperatures[st.peek()]) {
                st.push(i);
            }else {
                while(!st.isEmpty() && temperatures[i] > temperatures[st.peek()]) {
                    res[st.peek()] = i - st.peek();
                    st.pop();
                }
                st.push(i);
            }
        }
        return res;
    }
}

496.下一个更大元素 I
题目链接：496.下一个更大元素 I
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰下一个更大元素 I
日期：2024-10-20

想法：需要用一个hashmap来确定nums2中元素在不在nums1中，其余跟上面基本一样。
Java代码如下：

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Deque<Integer> st = new LinkedList<>();
        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);
        }
        st.push(0);
        for(int i = 1; i < nums2.length; i++) {
            if (nums2[i] <= nums2[st.peek()]) {
                st.push(i);
            } else {
                while(!st.isEmpty() && nums2[i] > nums2[st.peek()]) {
                    if(hashMap.containsKey(nums2[st.peek()])) {
                        Integer index = hashMap.get(nums2[st.peek()]);
                        res[index] = nums2[i];
                    }
                    st.pop();
                }
                st.push(i);
            }
        }
        return res;
    }
}

总结：
503.下一个更大元素II
题目链接：503.下一个更大元素II
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰下一个更大元素II
日期：2024-10-20

想法：对循环数组遍历两遍，用i % nums.length对应下标。
Java代码如下：

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int[] res = new int[nums.length];
        Arrays.fill(res, -1);
        Deque<Integer> st = new LinkedList<>();
        st.push(0);
        for(int i = 1; i < 2 * nums.length; i++) {
            if(nums[i % nums.length] <= nums[st.peek()]) {
                st.push(i % nums.length);
            }else {
                while(!st.isEmpty() && nums[i % nums.length] > nums[st.peek()]) {
                    res[st.peek()] = nums[i % nums.length];
                    st.pop();
                }
                st.push(i % nums.length);
            }
        }
        return res;
    }
}