# 739. Daily Temperatures

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

## solution

* 暴力

```python
class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        res = []
        for i in range(len(temperatures)):
            greater = False
            for j in range(i+1, len(temperatures)):
                if temperatures[j] > temperatures[i]:
                    res.append(j-i)
                    greater = True
                    break
            if not greater:
                res.append(0)
        return res
```

时间复杂度：O(n^2)\
空间复杂度：O()

* 单调栈

```python
class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        res = [0] * len(temperatures)
        stack = []

        for i, temp in enumerate(temperatures):
            # 求下一个更大: 单调栈保存的index递增，但index值递减。遇到大的，pop出来，同时更新pop index的结果
            while stack and temp > temperatures[stack[-1]]:
                j = stack.pop()
                res[j] = i - j
            stack.append(i)
        return res
```

时间复杂度：O(n)\
空间复杂度：O(n)

```python
class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        res = [0] * len(temperatures)  # 初始化一个默认值, 当不更新为自己, 因此初始化0
        stack = [0]  # 递增栈，对于第一个元素的判断，初始化一个比所有元素都小的

        for i in range(1, len(temperatures)):
            if temperatures[i] <= temperatures[stack[-1]]:
                stack.append(i)
            else:  # 注意 while
                while len(stack) != 0 and temperatures[i] > temperatures[stack[-1]]:
                    res[stack[-1]] = i - stack[-1]
                    stack.pop()
                stack.append(i)
        return res
```

## follow up

[84 Largest Rectangle in Histogram](https://longxingtan.gitbook.io/mle-interview/01_leetcode/dan-diao-zhan/84.-largest-rectangle-in-histogram)

[1019. Next Greater Node In Linked List](https://leetcode.com/problems/next-greater-node-in-linked-list/description/)

```python
class Solution:
    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:
        ans = []
        stack = []

        while head:
            while stack and head.val > ans[stack[-1]]:
                idx = stack.pop()
                ans[idx] = head.val

            stack.append(len(ans))
            ans.append(head.val)  # 由于整体大小不知道, 每次ans也append. 在单调栈while时进行合理修改
            head = head.next

        for i in stack:
            ans[i] = 0
        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://longxingtan.gitbook.io/mle-interview/01_leetcode/dan-diao-zhan/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.