[Leetcode] 739. Daily Temperatures
Given an array of integers temperaturesrepresents the daily temperatures, return an array answersuch that answer[i]is the number of days you have to wait after the i``thday to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0instead.
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 <= 10``5
30 <= temperatures[i] <= 100
How to understand?
return the answer array which stores the days to expect for warmer temperature than current temperature.
check the current temp in given input array, and update the answer array while checking the left day's temp in the array.
How to approach?
Brute Force
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
n = len(temperatures)
answer = [0] * n
for day in range(n):
for future_day in range(day + 1, n):
if temperatures[future_day] > temperatures[day]:
answer[day] = future_day - day
break
return answer
Literally check the left day's temperature to compare the current day's temperature, subtract the day from the found future day, and update the answer array.
Stack
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
n = len(temperatures)
answer = [0] * n
stack = []
for curr_day, curr_temp in enumerate(temperatures):
while stack and temperatures[stack[-1]] < curr_temp:
prev_day = stack.pop()
answer[prev_day] = curr_day - prev_day
stack.append(curr_day)
return answer
create answer array and fill with 0.
create stack.
in for loop, use curr_day as index and element value as curr_temp.
while condition to check if stack has length, and the temperature's element of stack's last index is less than curr_temp.
if it is true, then pop the last element in stack. set it as prev_day.
in answer array update the prev_day index elementa as the subtracted value of curr_day-prev_day.
This means as soon as we find the warmer day in temperatures, pop the elements in stack which is lower temperature than current day's temp.
and then append the curr_day index value.
lastly return the updated. answer array.
Skipping days using hottest day
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
n = len(temperatures)
hottest = 0
answer = [0] * n
for curr_day in range(n - 1, -1, -1):
current_temp = temperatures[curr_day]
if current_temp >= hottest:
hottest = current_temp
continue
days = 1
while temperatures[curr_day + days] <= current_temp:
days += answer[curr_day + days]
answer[curr_day] = days
return answer
this solution is using answer array itself to figure out the answer array.
create for loop iterate backwards from the end of temperatures array to the start.
create current temp using current day index.
use the hottest temp variable to detect the current_temp is the hottest value so far.
if it is then, update the hottest and continue to the next index(lower index)
and set days as 1 to follow up the future days temperature from the current day temperature.
while condition to check the current temp is greater than or equal to the future day temperature
if it is, then days will be updated with the answer's curr_day+days index element.
and then update the answer array's curr_day index with updated days.
lastly return the answer.
The key point is iterating temperatures array from the end to start point, and use the hottest variable to skip the days unrelated, use the answer array which has the information of how many days to skip from the current_day.