LeetCode 739. 每日温度

题目

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

例：
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

方法：暴力解法

class Solution(object):
    def dailyTemperatures(self, temperatures):
        answer = [0] * len(temperatures)
        for i in range(len(temperatures)):
            for j in range(i+1, len(temperatures)):
                if temperatures[i] < temperatures[j]:
                    answer[i] = j - i
                    break
        return answer

※ 超出时间限制

方法：单调栈

因为本题要求的是对于第 i 天，下一个更高温度出现在几天后，那么需要使用单调栈

• answer 记录每天的下一个更高温度出现在几天后
• stack 作为递增单调栈，存放元素在数组 temperatures 的下标
• 循环遍历，记录 answer
  • 若当前元素值小于等于栈顶元素值，那么需要将元素下标压入栈
  • 若当前元素值大于栈顶元素值，那么需要使用循环遍历，每次判断单调栈是否为空且当前元素与栈顶元素的大小关系。若单调栈非空且元素值大于栈顶元素值，那么记录此时单调栈的栈顶元素的 answer，其值为当前下标值减去栈顶元素下标值 i - stack[-1]，同时需要从单调栈中移除栈顶元素。并将此时的元素压入单调栈

class Solution(object):
    def dailyTemperatures(self, temperatures):
        answer = [0] * len(temperatures)
        stack = [0]
        for i in range(1, len(temperatures)):
            if temperatures[i] <= temperatures[stack[-1]]:
                stack.append(i)
            else:
                while len(stack) != 0 and temperatures[i] > temperatures[stack[-1]]:
                    answer[stack[-1]] = i - stack[-1]
                    stack.pop()
                stack.append(i)
        return answer

相关知识

• 单调栈：
  栈内元素按照单调递增或单调递减的顺序排列
  使用：寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置

参考

代码相关：https://programmercarl.com/0739.%E6%AF%8F%E6%97%A5%E6%B8%A9%E5%BA%A6.html