# 739.Daily-Temperatures

## 739. Daily Temperatures

## 题目地址

<https://leetcode.com/problems/daily-temperatures/>

## 题目描述

```
Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].
```

## 代码

### Approach #1 Stack

从右往左➡️，构建单调递减栈⏬

Time Complexity: O(N) && Space Complexity: O(W)

```java
class Solution {
  public int[] dailyTemperatures(int[] T) {
    int[] ans = new int[T.length];
    Stack<Integer> stack = new Stack();
    for (int i = T.length - 1; i >= 0; i--) {
      while (!stack.isEmpty() && T[i] >= T[stack.peek()]) {
        stack.pop();
      }

      if (stack.isEmpty()) {
        ans[i] = 0;
      } else {
        ans[i] = stack.peek() - i;
      }

      stack.push(i);
    }
    return ans;
  }
}
```

### Approach 2: Next Array

Time Complexity: O(NW) && Space Complexity: O(N + W)

```java
class Solution {
   public int[] dailyTemperatures(int[] T) {
    int[] ans = new int[T.length];
    int[] next = new int[101];
    Arrays.fill(next, Integer.MAX_VALUE);
    for (int i = T.length - 1; i >= 0; i--) {
      int warmer_index = Integer.MAX_VALUE;
      for (int t = T[i] + 1; t <= 100; t++) {
        if (next[t] < warmer_index) {
          warmer_index = next[t];
        }
      }
      if (warmer_index < Integer.MAX_VALUE) {
        ans[i] = warmer_index - 1; // -1 ?
      }
      next[T[i]] = i;
    }

    return ans;
   }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wentao-shao.gitbook.io/leetcode/stack/739.daily-temperatures.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.