能否将Haskell双遍扫描算法泛化至所有双指针问题？

接雨水的双遍扫描算法本质是双指针思路的「离线变体」——先预计算两侧极值再累积结果。要实现像泛化二分搜索、图搜索那样的通用双指针框架，我们可以提炼双指针问题的核心要素，构建可复用的抽象，而非局限于特定问题的逻辑。

通用双指针框架的Haskell实现 #

双指针问题的核心是通过左右指针的移动，结合维护的局部状态，高效完成累积计算。我们可以定义一个通用函数，将「初始状态」「移动决策」「累积逻辑」「终止条件」作为参数，让具体问题只需填充这些参数即可：

-- 通用双指针函数
-- 参数说明：
--   initState: 初始状态（包含左右指针位置、局部状态、累积结果）
--   shouldContinue: 判断是否继续循环的终止条件
--   step: 每一步的逻辑：根据当前状态，返回新的状态（指针移动、状态更新、累积值更新）
twoPointer :: s -> (s -> Bool) -> (s -> s) -> s
twoPointer initState shouldContinue step = go initState
  where
    go state
      | shouldContinue state = go (step state)
      | otherwise = state

这里的状态s可以是自定义元组，包含解决具体问题所需的所有信息——比如左右指针位置、当前两侧的极值、已累积的结果等。

用通用框架实现接雨水 #

我们可以把接雨水的逻辑映射到这个框架中，首先定义状态类型：

-- 接雨水问题的状态：左指针位置、右指针位置、左侧最大值、右侧最大值、已累积的雨水量
data RainState = RainState
  { leftPtr :: Int
  , rightPtr :: Int
  , leftMax :: Int
  , rightMax :: Int
  , total :: Int
  } deriving (Show)

然后定义初始状态、终止条件、每一步的逻辑：

-- 初始状态：左指针在0，右指针在末尾，初始极值为对应位置的值，累积量为0
initRainState :: [Int] -> RainState
initRainState xs = RainState
  { leftPtr = 0
  , rightPtr = length xs - 1
  , leftMax = xs !! 0
  , rightMax = xs !! (length xs - 1)
  , total = 0
  }

-- 终止条件：左右指针相遇时停止
rainContinue :: RainState -> Bool
rainContinue s = leftPtr s < rightPtr s

-- 每一步的逻辑：根据左右极值的大小移动指针，更新极值和累积量
rainStep :: [Int] -> RainState -> RainState
rainStep xs s
  | leftMax s <= rightMax s =
      let newLeft = leftPtr s + 1
          currentVal = xs !! newLeft
          newLeftMax = max (leftMax s) currentVal
          -- 当当前值小于左侧最大值时，累积差值；否则不累积
          newTotal = total s + max 0 (newLeftMax - currentVal)
      in s { leftPtr = newLeft, leftMax = newLeftMax, total = newTotal }
  | otherwise =
      let newRight = rightPtr s - 1
          currentVal = xs !! newRight
          newRightMax = max (rightMax s) currentVal
          newTotal = total s + max 0 (newRightMax - currentVal)
      in s { rightPtr = newRight, rightMax = newRightMax, total = newTotal }

-- 基于通用框架的接雨水实现
rainfallGeneric :: [Int] -> Int
rainfallGeneric [] = 0
rainfallGeneric xs = total $ twoPointer (initRainState xs) rainContinue (rainStep xs)

这个实现和原双遍扫描算法的结果一致，但它基于通用双指针框架构建。原算法是先预计算所有极值再求和，而这个在线双指针版本则在移动过程中实时计算累积量，两者本质都是利用了「两侧极值约束」的核心逻辑。

泛化到其他双指针问题 #

这个框架可以轻松扩展到其他经典双指针问题：

• 盛最多水的容器：修改step中的累积逻辑，改为计算当前指针位置的容器面积，并记录最大值
• 有序数组的两数之和：调整状态中的累积逻辑，改为寻找满足和为目标值的指针位置
• 三数之和：外层循环固定一个元素，内层用双指针寻找另外两个元素的组合

这种泛化是非平凡的——它不是简单的类型替换，而是提炼了双指针问题的核心控制流，让不同问题可以复用同一套框架，只需定制状态和每一步的逻辑。

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