【Hot100】LeetCode—739. 每日温度

1- 思路

单调栈

寻找当前位置的下一个比他大的元素的位置
利用 Stack 栈维护一个单调栈
- 当前元素 <= 栈顶元素，直接压栈
- 否则
  - 利用 while 循环判断

2- 实现

⭐739. 每日温度——题解思路

在这里插入图片描述

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int len = temperatures.length;
        int[] res = new int[len];
        if(len == 0 || temperatures==null){
            return res;
        }

        Stack<Integer> st = new Stack<>();
        
        // 单调 递增，比 poll 顶小的直接压栈
        // 否则弹出更新结果，栈存储的是下标
        st.push(0);
        for(int i = 1 ; i < len ; i++){
            int nowNum = temperatures[i];
            if(nowNum<= temperatures[st.peek()]){
                st.push(i);
            }else{
                while(!st.isEmpty() && nowNum > temperatures[st.peek()]){
                    res[st.peek()] = i-st.peek();
                    st.pop();
                }
                st.push(i);
            }
        }

        return res;
    }
}

3- ACM 实现

public class temperature {


    public static int[] dailyT(int[] temperature){
        // 计算每日温度
        int len = temperature.length;
        int[] res = new int[len];
        if(len==0 || temperature== null){
            return res;
        }
        // 单调栈
        Stack<Integer> st = new Stack<>();
        st.push(0);
        for(int i = 1 ; i < len;i++){
            int nowNum = temperature[i];
            if(nowNum<= temperature[st.peek()]){
                st.push(i);
            }else{
                while (!st.isEmpty() && nowNum>temperature[st.peek()]){
                    res[st.peek()] = i - st.peek();
                    st.pop();
                }
                st.push(i);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.nextLine();
        String[] parts = input.split(" ");
        int[] nums = new int[parts.length];
        for(int i = 0 ; i < parts.length;i++){
            nums[i] = Integer.parseInt(parts[i]);
        }
        int[] res = dailyT(nums);
        for(int i:res){
            System.out.print(i+" ");
        }
    }
}