LeetCode

Appearance

739. Daily Temperatures ​

题目 ​

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

 

Example 1:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Example 2:

Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Example 3:

Input: temperatures = [30,60,90]
Output: [1,1,0]

 

Constraints:

  • 1 <= temperatures.length <= 105
  • 30 <= temperatures[i] <= 100
Related Topics
  • 栈
  • 数组
  • 单调栈

  • 👍 1990
  • 👎 0

    • 思路 ​

    单调栈的典型题录，单调栈是用空间换取时间的操作

    • 元素和目标元素之间需要确定大小关系，入栈时标记坐标
    • 如果找目标元素大的元素，则栈底最大-栈顶最小，新元素和栈顶比较，一直出栈到新元素为最小元素
    • 如果找目标元素小的元素，则反之

    解法 ​

    py
    # leetcode submit region begin(Prohibit modification and deletion)
from typing import List
class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:

        res = [0] * len(temperatures)
        stack = []

        for i in range(len(temperatures)):

            while stack and temperatures[i] > temperatures[stack[-1]]:
                top_index = stack.pop()
                res[top_index] = i - top_index
            stack.append(i)

        return res

Solution().dailyTemperatures([73,74,75,71,69,72,76,73])
        
# leetcode submit region end(Prohibit modification and deletion)

    复杂度分析 ​

    N 为数组的长度

    • 时间复杂度 O(N)
    • 空间复杂度 O(N)