739. 每日温度

Powered by:NEFU AB-IN

Link

739. 每日温度

题意

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

思路

单调栈模板题

单调栈：栈中存储的是温度的索引，并且保证栈中的温度是单调递减的，也就是栈中是没设置右边更高温度的温度下标。这样可以确保一旦出现当前温度比栈顶温度高的情况，栈顶温度的升高天数就可以确定。

从前往后遍历：对于每个温度temp，先检查栈是否为空且temp是否大于栈顶的温度（通过索引stack_[-1]访问栈顶温度）。
如果temp大于栈顶温度，说明找到了一天温度更高的日子，于是弹出栈顶索引j，并计算出天数差i - j，将其存入结果数组res_。
继续检查下一个栈顶元素，直到栈为空或当前温度不再大于栈顶温度为止。
将当前温度的索引i压入栈中。

代码

'''
Author: NEFU AB-IN
Date: 2024-08-27 16:39:14
FilePath: \LeetCode\739\739.py
LastEditTime: 2024-08-27 16:42:35
'''
# 3.8.19 import
import random
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache, reduce
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, comb, fabs, floor, gcd, hypot, log, perm, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin
from typing import Any, Callable, Dict, List, Optional, Tuple, TypeVar, Union# Constants
TYPE = TypeVar('TYPE')
N = int(2e5 + 10)
M = int(20)
INF = int(1e12)
OFFSET = int(100)
MOD = int(1e9 + 7)# Set recursion limit
setrecursionlimit(int(2e9))class Arr:array = staticmethod(lambda x=0, size=N: [x() if callable(x) else x for _ in range(size)])array2d = staticmethod(lambda x=0, rows=N, cols=M: [Arr.array(x, cols) for _ in range(rows)])graph = staticmethod(lambda size=N: [[] for _ in range(size)])class Math:max = staticmethod(lambda a, b: a if a > b else b)min = staticmethod(lambda a, b: a if a < b else b)class Std:pass# ————————————————————— Division line ——————————————————————class Solution:def dailyTemperatures(self, temperatures: List[int]) -> List[int]:res_ = Arr.array(0, len(temperatures))stack_ = []for i, temp in enumerate(temperatures):while stack_ and temp > temperatures[stack_[-1]]:j = stack_.pop()res_[j] = i - jstack_.append(i)return res_