739 Daily Temperatures

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

solution

• 暴力

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()

• 单调栈

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)

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

1019. Next Greater Node In Linked List

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