LeetCode739每日温度

题目描述

  给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

解析

  每次往栈中添加下标，如果遇到比栈顶元素对应的温度高，说明找到了栈顶的温度，出栈并入栈当前温度。

public int[] dailyTemperatures(int[] temperatures) {
        int[] res = new int[temperatures.length];
        Deque<Integer> s = new LinkedList<>();
        s.push(0);
        for(int i = 1; i < temperatures.length; i++) {
            while (!s.isEmpty() && temperatures[s.peek()] < temperatures[i]) {
                int pre = s.pop();
                res[pre] = i - pre;
            }
            s.push(i);
        }
        return res;
    }

  时间消耗最少的方式是动态规划，从后往前遍历：

• 如果第 i+1 天的温度大于第 i 天的温度，那么 dp[i] = 1。
• 如果第 i+1 天的温度不大于第 i 天的温度，那么查看 dp[i+1]：
  • 如果 dp[i+1] 是非零的，说明从第 i+1 天开始，有一个已知的更热的天在 i+1 + dp[i+1]。接下来检查那一天的温度是否高于第 i 天：
    • 如果是，dp[i] 就是 1 + dp[i+1]。
    • 如果不是，继续向后查看，直到找到更热的一天或者查看到数组的尽头。

public int[] dailyTemperatures(int[] temperatures) {
        int n=temperatures.length;
        int[] dp=new int[n];
        for(int i=n-2;i>=0;i--){
            int j=i+1;
            while(j<n && temperatures[j]<=temperatures[i] && dp[j]!=0){
                j+=dp[j];
            }
            if(j<n &&temperatures[j]>temperatures[i]){
                dp[i]=j-i;
            }
        }
        return dp;
    }

  虽然从此题提交的结果来看，动态规划耗时更短，但是使用栈，最好最坏的复杂度都是O(n)，而使用动态规划最好为O(n)，最坏是O(n^2)，因此实际开发还是建议使用栈的方式来解决问题。