Leetcode739 - Daily Temperatures

题目描述

Leetcode 739 本题考察了栈的使用。题目输入是一段温度值列表，然后返回一个列表。这个列表包含了输入列表中每一天还有多少天温度升高。如果未来没有升高的情况，则输入 0。

# Example1:

# Input: T = [73, 74, 75, 71, 69, 72, 76, 73]

# Output: [1, 1, 4, 2, 1, 1, 0, 0]

# 比如 index=0 这天温度为 73 度，index=1，这天为 74 度。

# 所以针对 index=0 这天，还需要 1 天温度会升高。

# 对于 index=2 这天，还需要 4 天才可以温度升高。

题目分析

通常的做法是从某一位置开始依次和该位置之后的温度进行比较，但这样就会出现冗余的情况。

拿 index=2 的温度来说，会和 71,69,72,76 依次做比较。但实际上经过此次比较，71,69 已

经找到比它本身温度高的答案了，复杂度为 O(N^2)

可以使用栈进行保存，栈里面保存的是当前栈顶元素的下标。而当前遍历元素的下标减去栈顶元素的

下标就是所需要经历的天数。每个元素最多被弹出和压入栈一次，因此为 O(N).

# Question: Daily Temperatures

# Given a list of daily temperatures T, return a list such that, for each day in

#  the input, tells you how many days you would have to wait until a warmer

#  temperature. If there is no future day for which this is possible, put 0

#  instead.

# Example1:

# T = [73, 74, 75, 71, 69, 72, 76, 73]

# [1, 1, 4, 2, 1, 1, 0, 0]

# Note:

# the length of temperatures will be in the range [1, 30000]

# Each temperature will be an integer in the range [30, 100]

class Solution(object):

    def dailyTemperatures(self, T):

        """

        :type T: List[int]

        :rtype: List[int]

        """

        stack = []

        stack_sky = [0] * len(T)

        for index, element in enumerate(T):

            if stack.__len__() > 0:

                tem = T[stack[-1]]

                while stack and element > tem:

                    stack_sky[stack[-1]] = index - stack[-1]

                    stack.pop()

                    if stack.__len__() > 0:

                        tem = T[stack[-1]]

            stack.append(index)

        return stack_sky

if __name__ == '__main__':

    example_list_1 = [73, 74, 75, 71, 69, 72, 76, 73]

    example_list_2 = [89, 62, 70, 58, 47, 47, 46, 76, 100, 70]

    solution = Solution()

    print(solution.dailyTemperatures(example_list_2))

巴特西

Leetcode739 - Daily Temperatures

题目描述

题目分析

最新文章

热门文章