问题
问题描述：给定一个每日温度的列表 T，要求返回一个列表，计算出每天的温度还需等待要多少天才能比当前温度高，如果没有，设置为 0。
问题要点：对于每个元素来说，只需向后找到比其大的第一个数，然后计算 index 之差。
栗子：
输入： T = [73, 74, 75, 71, 69, 72, 76, 73]
输出：[1, 1, 4, 2, 1, 1, 0, 0]
注意：1 <= T.count <= 3000，33 <= temperature <= 100
想看英文的戳这里：原题地址
解题思路
常规解法
对于每个元素，只需要从其 index + 1 开始遍历，找到第一个比它大的数。代码很容易写出，两层 for 循环搞定。
func dailyTemperatures(_ T: [Int]) -> [Int] {
var i = 0
var j = 0
var result = [Int]()
while i < T.count {
j = i
// 找到第一个比它大的数
while j < T.count, T[j] <= T[i] {
j += 1
}
if j != T.count {
result.append(j - i)
} else {
result.append(0)
}
i += 1
}
return result
}
但是，提交结果却是超时。我们可以比较容易分析出其时间复杂度为 O(n^2)，而 1 <= n <= 3000，最高会达到百万次的遍历，所以还是比较耗时的。
所以下一步的方案，要减少遍历次数。
我的解法
思路：将温度按升序排序，并记录其原始对应的 index，当计算 t 时，找到所有比其大的数，计算出最小的 index 之差，注意 index 需为正数（因为有可能存在前面的温度比 t 大）。
因为 t 在 [33, 100] 之间，所以最多也就 100 - 30 + 1 = 71 中温度。计算出每种温度所包含的 index 列表，用 map 存储，map[t] = indexList。
对于 T 中的每个元素 t，遍历 map 的 key（表示温度），如果 key > t，则取其 indexList，从中找到离它最近的 index 即可。
代码如下：
// 20.25%
func dailyTemperatures_2(_ T: [Int]) -> [Int] {
// 记录 temperature 所对应的 index
var map = [Int: [Int]]()
var result = [Int]()
var i = 0
while i < T.count {
if var list = map[T[i]] {
list.append(i)
map[T[i]] = list
} else {
map[T[i]] = [i]
}
i += 1
}
let sorted = map.keys.sorted()
i = 0
while i < T.count {
if var curTmpList = map[T[i]], curTmpList.count > 0 {
var j = 0
// 找到离它最近的数
var minIndex = Int.max
while j < sorted.count {
if sorted[j] > T[i] {
// 找到在其后的index
let tmpList = map[sorted[j]]!
for index in tmpList {
if index > i {
if index < minIndex {
minIndex = index
}
break
}
}
}
j += 1
}
if minIndex != Int.max {
result.append(minIndex - i)
} else {
result.append(0)
}
// 该数已经处理过了，删除
curTmpList.remove(at: 0)
map[T[i]] = curTmpList
}
i += 1
}
return result
}
更高效的解法-从后往前
使用数组
这种解法比上面的更优，时间复杂度为 O(N * W)，N 为 T 的长度，W 为可能温度的种数 71，所以复杂度可认为是 O(N。
从后往前计算，记录每种温度最近的位置。由于最多只有 71 种温度，以空间换时间，初始化 record[100] 数组，每种温度的初始值位置为 Int.max，如果某种温度在列表中出现，则更新其位置 record[i] = index。
其实使用 map 存储也可以。
代码如下：
// 由于温度的范围在 [30,100] 之间，对应 T[i]，遍历 T[i] + 1 ... 100，寻找最近的值
func dailyTemperatures_3(_ T: [Int]) -> [Int] {
var result = [Int]()
// 记录已经出现元素的位置
var record = [Int]()
// 设置初始值
var i = 0
while i <= 100 {
record.append(Int.max)
i += 1
}
// 倒序遍历
i = T.count - 1
while i >= 0 {
// 从比它高的温度开始
var j = T[i] + 1
var index = Int.max
// 计算最近的位置
while j <= 100 {
if record[j] < index {
index = record[j]
}
j += 1
}
// 有比其高的温度
if index != Int.max {
result.insert(index - i, at: 0)
} else {
result.insert(0, at: 0)
}
// 记录位置
record[T[i]] = i
i -= 1
}
return result
}
使用栈
栈中存的是 index，同样是从后前往计算，时间复杂度为 O(n)，与上面的分析类似。
- 逐个遍历栈中的数据所对应的温度，若比当前温度小，则出栈；若比当前温度高，则停止遍历，因为越靠后的数，越靠近栈底。
- 判断当前栈是否为空，为空则为
0，否则取出栈顶的index计算差值。 - 将当前温度的
index入栈。
代码如下：
func dailyTemperatures_4(_ T: [Int]) -> [Int] {
// 用数组模拟栈
var stack = [Int]()
var record = [Int]()
var i = 0
while i < T.count {
record.append(0)
i += 1
}
i = T.count - 1
while i >= 0 {
// 倒序遍历，模拟栈
var j = stack.count - 1
while j >= 0 {
// 如果当前温度高，出栈删除
if T[i] >= T[stack[j]] {
stack.remove(at: j)
}
j -= 1
}
if stack.isEmpty {
record[i] = 0
} else {
record[i] = stack.last! - i
}
// 进栈
stack.append(i)
i -= 1
}
return record
}
