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)，因此实际开发还是建议使用栈的方式来解决问题。