IT 面试题库

编程题:每日温度(LeetCode 739):给定每日气温数组,对每天求「还要等几天才会升温」,没有则填 0,要求优于 O(n²)。请解释单调栈为什么能把复杂度降到 O(n)。

高级编程题算法工程师Java后端工程师单调栈下一个更大元素LeetCode739复杂度分析

题目

考察点:单调栈的核心模型——「下一个更大元素」。追问:栈里存下标还是存值?为什么?

参考答案

内容深度:适中 · 含示例/代码 · 来源:外部链接 · 未复核 · 72 天前更新 · 技术内容可能随版本变化,建议结合官方文档理解

要点:维护一个下标单调递减的栈(栈顶到栈底温度递增的反向),遇「更大值」时批量弹栈结算。

def dailyTemperatures(T):
    ans = [0] * len(T)
    stack = []  # 存下标,对应温度单调不增
    for i, t in enumerate(T):
        while stack and T[stack[-1]] < t:
            j = stack.pop()
            ans[j] = i - j       # i 是 j 右侧第一个更大下标
        stack.append(i)
    return ans
练这道题

同分类 · 高频题

题目与答案就在本页;收藏、批注和错题重练在应用内

这道题看完了?连刷同类题,趁热打铁效果最好 进入刷题