What is the stack-based state management pattern?

The stack-based state management pattern uses a stack to maintain and process states, often used in problems where you need to compare elements or track changes over time, like finding the next warmer day.

How does the stack approach optimize the Daily Temperatures problem?

By using a monotonic stack, we can efficiently track the next warmer day in a single pass through the temperatures array, ensuring both time and space optimization.

What are the common mistakes when solving Daily Temperatures?

The common mistakes include failing to properly manage the stack, using inefficient time complexity, and forgetting to return 0 when no warmer day exists.

Can this problem be solved using a brute-force approach?

Yes, but it would have a time complexity of O(n^2), as it would involve nested loops to compare each day with every other day. The stack approach improves this to O(n).

What other variations of the Daily Temperatures problem exist?

Variations include finding the cooler days, determining the temperature on the waiting day, or handling multiple cities' temperature data in a similar way.

#739

Medium

auto_awesome栈·状态

LeetCode 题解工作台

每日温度

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

数组栈单调栈

题目描述

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

示例 1:

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

示例 2:

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

输入: temperatures = [30,60,90]
输出: [1,1,0]

提示：

1 <= temperatures.length <= 10⁵
30 <= temperatures[i] <= 100

lightbulb

解题思路

方法一：单调栈

本题需要我们找出每个元素右边第一个比它大的元素的位置，这是一个典型的单调栈应用场景。

我们从右往左遍历数组 $\textit{temperatures}$ ，维护一个从栈顶到栈底温度单调递增的栈 $\textit{stk}$ ，栈中存储的是数组元素的下标。对于每个元素 $\textit{temperatures}[i]$ ，我们不断将其与栈顶元素进行比较，如果栈顶元素对应的温度小于等于 $\textit{temperatures}[i]$ ，那么循环将栈顶元素弹出，直到栈为空或者栈顶元素对应的温度大于 $\textit{temperatures}[i]$ 。此时，栈顶元素就是右边第一个比 $\textit{temperatures}[i]$ 大的元素，距离为 $\textit{stk.top()} - i$ ，我们更新答案数组。然后将 $\textit{temperatures}[i]$ 入栈，继续遍历。

遍历结束后，返回答案数组即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $\textit{temperatures}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stk = []
        n = len(temperatures)
        ans = [0] * n
        for i in range(n - 1, -1, -1):
            while stk and temperatures[stk[-1]] <= temperatures[i]:
                stk.pop()
            if stk:
                ans[i] = stk[-1] - i
            stk.append(i)
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n) due to the single pass through the temperatures array. Space complexity is O(n) because we use a stack to store indices of the temperatures.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
This problem tests the candidate’s ability to efficiently manage stack-based state in an array.
question_mark
The candidate should demonstrate familiarity with monotonic stacks, a key pattern in algorithmic optimization.
question_mark
The interviewer should look for a solution that optimizes both time and space complexities, ideally in O(n) time.

warning

常见陷阱

外企场景

error
A common mistake is not properly managing the stack and not popping elements at the correct time.
error
Another pitfall is inefficient time complexity, such as using nested loops instead of a single pass through the array.
error
Forgetting to return 0 when no warmer day exists is another error that can affect correctness.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Given the temperatures of multiple cities, find the days to wait for a warmer temperature for each city.
arrow_right_alt
Use a similar approach to determine how many days you have to wait for a cooler temperature instead.
arrow_right_alt
Modify the problem to return the actual temperature for each day, not just the number of days.

help

常见问题

外企场景

继续练习

#768 最多能完成排序的块 II #769 最多能完成排序的块 #654 最大二叉树