739.每日温度

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

一、栈

类似496. 下一个更大元素 I的解法二。用一个栈存储待求的日期下标。i遍历T数组，遇到比栈顶温度高的就出栈，并计算相差天数，写入res

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        n = len(T)
        if n == 1:
            return [0]
        res = [0] * n    #结果集，初始为0
        stack = [0]    #栈，存储下标
        for i in range(1, n):
            #比较当前温度与栈顶下标指示的温度
            while len(stack) > 0 and T[i] > T[stack[-1]]:
                res[stack[-1]] = i - stack[-1]    #计算差值
                stack.pop()
            stack.append(i)    #每次入栈一个
        return res

二、单调栈

类似496. 下一个更大元素 I的解法三

i从后往前反向遍历，元素下标依次入栈，构造一个单调栈，保持栈底最大，栈顶最小。每次i与栈顶比较，若t[i]大于等于栈顶则弹栈，即栈顶是最靠近i的最大元素，再计算下标差值即可

class Solution:
    def dailyTemperatures(self, t) :
        n = len(t)
        res = [0]*n
        stack = []
        for i in range(n-1, -1, -1):	#元素依次入栈
            #栈非空，且扫到不小于栈顶的，则弹栈
            while stack and t[stack[-1]] <= t[i]:
                stack.pop()
            res[i] = stack[-1] - i if stack else 0
            stack.append(i)
        return res