[PYTHON] Let Code Day 50 "739. Daily Temperatures" Starting from Zero

Overview

It seems that coding tests are conducted overseas in interviews with engineers, and in many cases, the main thing is to implement specific functions and classes according to the theme.

As a countermeasure, it seems that a site called Let Code will take measures.

A site that trains algorithmic power that can withstand coding tests that are often done in the home.

I think it's better to have the algorithm power of a human being, so I'll solve the problem irregularly and write down the method I thought at that time as a memo.

Leetcode

Leet Code Table of Contents Starting from Zero

Last time Leet Code Day49 starting from zero "1323. Maximum 69 Number"

Right now, I'm prioritizing the Medium of the Top 100 Liked Questions. I solved all Easy, so if you are interested, please go to the table of contents.

Twitter I'm doing it.

50 times! 50 times!

problem

739. Daily Temperatures The difficulty level is Medium. Excerpt from Top 100 Liked Questions.

The problem is given a list of Ts that stores the temperatures for each day. Design an algorithm that returns a list showing how many days it will take for those elements to reach warmer temperatures than each day of input.

For example, if T = [73, 74, 75, 71, 69, 72, 76, 73], the returned list will be [1, 1, 4, 2, 1, 1, 0, 0]. I will.

It is assumed that the length of temperature is given between [1,30000] and each temperature is given between [30,100].

When you see the problem, what's the first? ?? Why is the output like this? I thought, but when I looked closely, I found that my understanding was low.

It's not about the difference from the next day, but simply how many days later the temperature will exceed that day.

solution

First, I prepared a list with 0s for the length of the element, and I thought it would be easy to understand how to lick the list obediently. If you use stack, it's LIFO, so it will be easier to implement.

In the case of the example, prepare stack and [0] first for the length of T. Let's lick the list from there.

What is important here is what kind of conditioning should be used for assignment, and what kind of processing should be performed to shift the elements.

In this case, only if stack exists and T [stack [-1]] is larger than the element when licking from the front, the element of ʻansis popped and the element It means that you should put the one obtained by subtracting the last element ofstack` from the order of.

Then, if you add an index to stack and repeat until there are no more elements, you can get the required number of days for each schedule in ʻans`.

I wrote the flow so far.

class Solution(object):
    def dailyTemperatures(self, T):
        ans,stack = [0] * len(T),[]
        for i, j in enumerate(T):
            while stack and T[stack[-1]] < j:
                ans[stack.pop()] = i - stack[-1]
            stack.append(i)
        return ans
# Runtime: 548 ms, faster than 32.01% of Python3 online submissions for Daily Temperatures.
# Memory Usage: 17.1 MB, less than 95.07% of Python3 online submissions for Daily Temperatures.

It is the familiar ʻenumerate`. In the for loop, you can get the index number (count, order) at the same time as the element of the iterable object such as a list (array), and it is an excellent thing that you can get both such count and order and assign it to a variable. is.

I had an Easy problem several times, so I used my head like this for the first time in a while. If you think about it carefully, you can think of a distance between two points.

Up to here for this time. Thank you for your hard work.