> For the complete documentation index, see [llms.txt](https://longxingtan.gitbook.io/mle-interview/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://longxingtan.gitbook.io/mle-interview/01_leetcode/dan-diao-zhan/739.-daily-temperatures.md).

# 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](/mle-interview/01_leetcode/dan-diao-zhan/84.-largest-rectangle-in-histogram.md)

[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
```