[Notes] 2020.6.11 每日一题

题目

根据每日 气温 列表,请重新生成一个列表,对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高,请在该位置用 0 来代替。

例如,给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73],你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示:气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度,都是在 [30, 100] 范围内的整数

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/daily-temperatures
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

  1. 最简单,多层for循环搜索。复杂度O(n^2)
  2. 官方思路,单调栈。复杂度O(n)
  3. 官方思路,自后向前遍历。复杂度O(mn)

思路2是通过大空间换时间,首先构建温度30100每个温度第一次出现的下标记录表,这样从后向前遍历的时候,每遍历到一个温度值t,就在表格中搜索t100度之间,第一次出现下标里最小的值,那个值就是下一次比t温度高的天的index。

思路3是通过遍历一次数组,将每个高值对应的多个低值相应的间隔统一设置。

这里的重点是多对一映射,应该由一向多去遍历;有意思的是单调栈这么个结构。

单调栈顾名思义,就是栈中的元素有对应的递增或者递减关系。这意味这个栈适用维护一种的排序关系的情况,因为栈的动态性,这种结构应该比较适合动态维护一种单调的排序关系。但是它和堆、红黑树又不一样,它因为有着栈的特性——后进先出,因此适用于多对一的局部排序(例如,对于递增栈,新元素比栈顶元素大,则栈顶元素要退栈),因此这个结构并不强调元素之间全面的比较。

解法

思路1:

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        length = len(T)
        result = [0 for i in range(length)]
        for i in range(length):
            aa = T[i]
            for j in range(i, length):
                if T[j] > aa:
                    result[i] = j - i
                    break
        return result

注意,这个会超时。

思路2:

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        length = len(T)
        result = [0] * length
        stack = []
        for i in range(length):
            current = T[i]

            while len(stack)>0 and current > T[stack[-1]]:
                tmpIndex = stack.pop()
                result[tmpIndex] = i - tmpIndex

            stack.append(i)
        return result

思路3:

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        length = len(T)
        result = [0] * length
        tmpTable = {}
        MAX_VALUE = 300001

        for i in range(length-1,-1,-1):
            tmpTable[T[i]] = i
            tmpMinT = MAX_VALUE
            for j in range(T[i]+1,101):
                if (j in tmpTable) and (tmpTable[j] < tmpMinT):
                    tmpMinT = tmpTable[j]
            result[i] = tmpMinT - i if tmpMinT != MAX_VALUE else 0
        return result
上一篇:2020 Cybrics CTF Web Writeup


下一篇:golang notes(2)