算法-每日温度题解

Problem: 739. 每日温度 (opens new window)

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

示例 1:

输入:temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

# 暴力求解

这道题最先想到的思路就是暴力法，如果要得比当天温度距离接下来更高温度的天数，最简单的方法就是遍历当前温度后面天数的温度，当遍历到的温度大于当前元素温度，就用下标计算得到差值即可，代码如下：

func dailyTemperatures(_ temperatures: [Int]) -> [Int] {
    var index = 0
    var newArr = [Int]()
    while index < temperatures.count {
        let value = temperatures[index]
        var nextIndex = index + 1
        while nextIndex < temperatures.count {
            let nextValue = temperatures[nextIndex]
            if value < nextValue {
                newArr.append(nextIndex-index)
                break
            }
            nextIndex = nextIndex + 1
        }
        if nextIndex == temperatures.count {
            newArr.append(0)
        }
        index = index + 1
    }
    return newArr
}

这种解法的时间复杂度是 O(n^2)，除去返回值的空间复杂度是 O(1)

# 单调栈解法

单调栈本质上对应的数据结构就是栈，只不过栈内的元素是有序的。

单调栈本质上是用空间换时间的做法，从头开始遍历，得到的元素放入栈中，**栈中存放的元素是没有遇到比他们温度更大的元素，**所以这里的单调栈是单调递减栈。当遍历到后面的元素的时候，去和栈顶的元素进行比较。

  • 如果新遍历到的元素比栈顶元素大。说明后面的元素的温度比当前栈顶元素温度大，将栈顶元素弹出，并通过下标差值得到栈顶元素温度对应的比它更高的温度的距离天数。注意这个过程是持续过程，直到新元素比栈顶元素温度要小。
  • 如果新遍历的元素和栈顶元素相同。说明两者温度一样，栈顶元素并没有遇到比它更大的温度元素，所以直接将元素入栈就好了。
  • 如果新遍历的元素比栈顶元素小。依然说明栈顶元素并没有遇到比它更大的温度元素，所以直接将元素入栈就好了。

最终的解法是

func dailyTemperatures(_ temperatures: [Int]) -> [Int] {
    var res = [Int].init(repeating: 0, count: temperatures.count)
    var stack = [Int]()
    for (index, temperature) in temperatures.enumerated() {
        if stack.isEmpty == false {
            while stack.isEmpty == false && temperature > temperatures[stack.last!] {
                res[stack.last!] = index - stack.last!
                stack.removeLast()
            }
            if stack.isEmpty == false {
                if temperature < temperatures[stack.last!] {
                    stack.append(index)
                } else if temperature == temperatures[stack.last!] {
                    stack.append(index)
                } else {
                    //
                }
            } else {
                stack.append(index)
            }
        } else {
            stack.append(index)
        }
    }
    return res
}

精简下分支代码如下

func dailyTemperatures(_ temperatures: [Int]) -> [Int] {
    var res = [Int].init(repeating: 0, count: temperatures.count)
    var stack = [Int]()
    for (index, temperature) in temperatures.enumerated() {
        while stack.isEmpty == false && temperature > temperatures[stack.last!] {
            let lastIndex = stack.removeLast()
            res[lastIndex] = index - lastIndex
        }
        stack.append(index)
    }
    return res
}

最新解法的时间复杂度是 O(n)，空间复杂度是 O(n)

暴力求解
单调栈解法