# 739. Daily Temperatures

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2F3gZn4JN5Vd9zYdNz25uq%2F%E5%9C%96%E7%89%87.png?alt=media\&token=4133a39f-4f95-4bb4-aef8-134f170fe3de)



## naive - two pointers

T: O(n^2)

T: O(n), **with ans result**

```java
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] res = new int[n];
        int i = 0;
        int j = 1;
        while (i < n && j < n) {
            while (j < n && temperatures[j] <= temperatures[i]) {
                j++;
            }
            if (j < n) {
                res[i] = j-i;
            }
            i++;
            j = i+1;
        }
        return res;
    }
}
/*
 1. two pinters
 2. if find, the ans is (j-i), if next i, j set to i the same position
 
 
 [55,38,53,81,61,93,97,32,43,78]
                    i
                          j
  3   1  1  2  1 1  

*/
```



## mono stack (decresing, 注意要判斷 decresing or increasing

```
[73,74,75,71,69,72,76,73]
 [1,1,  4, 2, 1, 1,0,0]
 
 
[ 75,71,69] in decresing stack , meets 72 > peek(), start to pop
```

T: O(n)

S: O(n), **with ans result and stack**

```java
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] res = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();
        
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int idx = stack.pop();
                res[idx] = i - idx;
            }
            stack.push(i);
        }
        return res;
    }
}
```



## **Array, Optimized Space**

**no stack**

T: O(n)

S: O(n)**, with ans result**

[**https://leetcode.com/problems/daily-temperatures/solution/**](https://leetcode.com/problems/daily-temperatures/solution/)
