在Haskell中实现每日气温问题：无需Data.Map的O(n log n)解法探讨

问题描述 #

给定整数数组temperatures表示每日气温，返回数组answer，其中answer[i]为第i天后需要等待的天数，直至遇到气温更高的日子；若不存在这样的未来日期，则answer[i] = 0。

现有实现 #

我已通过以下几种方式实现该功能：

基于列表与Map的实现 #

warmer :: [Int] -> [Int]
warmer = M.elems . go [] . zip [0..]
  where
    go stack [] = foldr ((`M.insert` 0) . fst) M.empty stack
    go [] ((i,x):rest) = go [(i,x)] rest
    go ((j,y):stack) ((i,x):rest)
      | x > y     = M.insert j (i-j) (go stack ((i,x):rest))
      | otherwise = go ((i,x):(j,y):stack) rest

基于Vector的实现 #

warmer' :: Vector Int -> Vector Int
warmer' xs = snd $ V.ifoldl' go ([], V.replicate (V.length xs) 0) xs
  where
    go ([]         , ys) i x = ([(i,x)], ys)
    go ((j,y):stack, ys) i x
      | x > y     = go (stack, ys // [(j,i-j)]) i x
      | otherwise = ((i,x):(j,y):stack, ys)

基于Vector与Map的实现 #

warmer'' :: Vector Int -> [Int]
warmer'' xs = M.elems $ snd $ V.ifoldl' go ([], M.fromAscList $ zip [0..] $ zipWith const [0,0..] (V.toList xs)) xs
  where
    go ([]         , days) i x = ([(i,x)], days)
    go ((j,y):stack, days) i x
      | x > y     = go (stack, M.insert j (i-j) days) i x
      | otherwise = ((i,x):(j,y):stack, days)

这些实现均较为繁琐，需借助Map转换等技巧规避输出的随机写入需求。我发现纯函数式语言中，需要O(1)随机访问数组/列表元素的算法往往难以优雅实现。

核心问题解答 #

1. 是否存在[Int] -> [Int]的O(n log n)复杂度解法，可避免随机写入？ #

存在。可以通过排序+有序集合查询的思路实现，无需依赖随机写入操作，代码风格更贴合纯函数式特性：

import qualified Data.Map as M
import qualified Data.Set as S
import Data.List (sortOn)
import Data.Foldable (foldl')

warmerOlogn :: [Int] -> [Int]
warmerOlogn temps = map getAnswer [0 .. length temps - 1]
  where
    indexed = zip [0 ..] temps
    -- 按温度降序排序，同温元素按索引降序排列，避免同温元素互相干扰
    sorted = sortOn (\(i, t) -> (-t, -i)) indexed
    -- 遍历排序后的元素，维护已处理的索引集合（对应温度更高的日期），构建答案Map
    (_, answerMap) = foldl' process (S.empty, M.empty) sorted
    process (set, map) (i, _) =
      case S.lookupGT i set of
        Just j -> (S.insert i set, M.insert i (j - i) map)
        Nothing -> (S.insert i set, M.insert i 0 map)
    -- 按原索引顺序提取答案
    getAnswer i = M.findWithDefault 0 i answerMap

这个实现的核心逻辑：

• 将所有日期的索引与温度配对，按温度从高到低排序，确保处理当前元素时，已处理集合中的元素都是温度更高的日期
• 用有序集合Data.Set存储已处理的索引，每次查询当前索引右侧第一个更大的索引（即未来第一个更热的日期），操作复杂度为O(log n)
• 最后通过Map存储每个索引的答案，再按原索引顺序生成结果列表，全程无随机写入操作

整体时间复杂度为O(n log n)，符合要求。

2. 合适的提问平台 #

针对这类Haskell函数式算法问题，推荐以下平台：

• Stack Overflow：用haskell和algorithm标签提问，清晰描述问题、现有代码和预期目标，能得到全球开发者的专业解答
• Haskell Discourse：Haskell官方社区论坛，专注于函数式编程、语言特性、算法实现等深度讨论
• Libera Chat #haskell频道：实时IRC交流平台，适合快速获取针对性反馈，注意遵守频道交流规则
• Reddit r/haskell板块：活跃的Haskell开发者社区，适合分享问题、讨论编程技巧和最佳实践

内容的提问来源于stack exchange，提问作者Brendan Langfield