Haskell实现数组双端Greedy algorithm的最佳实践

核心实现范式 #

相向双指针是数组类问题中时间效率极高的一类解法，通用实现逻辑可以固定为以下几步，几乎所有同类问题都可以直接套入框架，只需要调整状态计算逻辑即可：

• 初始化：左指针left指向数组首位置索引0，右指针right指向数组末位置索引n-1，同时初始化与问题匹配的两侧状态缓存变量（比如接雨水问题里需要记录左右两侧已遍历过的最大高度）、结果累计变量。
• 循环边界：统一以left <= right作为循环进入条件，若场景明确不需要处理两指针重合的最后一个元素，可以调整为left < right，整个遍历过程每个元素只会被访问一次，时间复杂度稳定为O(n)。
• 移动规则：每轮循环先比较左右指针当前指向的元素值，永远向数组中间移动值更小一侧的指针，这是整个贪心逻辑成立的核心——小值侧的约束已经被对侧的更大值锁定，不需要再额外遍历对侧元素就可以直接计算当前位置的结果。
• 状态更新：移动指针前，先判断当前位置值是否刷新了该侧的状态极值：如果是则更新极值记录，否则按照问题规则计算当前位置对结果的贡献值、累加到总结果中，完成后再移动指针。

案例：接雨水问题的双指针实现 #

问题描述：

给定n个代表高程图的非负整数，每个柱体宽度为1，计算降雨后总共可以截留的雨水量。

基于上述范式的C++贪心最优实现如下，空间复杂度仅为O(1)：

class Solution {
public:
    int trap(int A[], int n) {
        int left=0; int right=n-1;
        int res=0;
        int maxleft=0, maxright=0;
        while(left<=right){
            if(A[left]<=A[right]){
                if(A[left]>=maxleft) maxleft=A[left];
                else res+=maxleft-A[left];
                left++;
            }
            else{
                if(A[right]>=maxright) maxright= A[right];
                else res+=maxright-A[right];
                right--;
            }
        }
        return res;
    }
};

函数式语言的实现选型参考 #

很多喜欢Haskell的开发者会疑惑，这类带明显索引移动、状态累计特征的算法，是不是像OCaml那样支持回退到命令式编程实现会更优，实际上两者没有绝对的好坏：

• 纯函数式尾递归实现完全可以覆盖需求：把左右指针、两侧极值、累计结果都作为尾递归函数的入参，逻辑和命令式循环完全等价，Haskell编译器会对尾递归做优化，生成的机器码效率和循环写法没有量级差异，代码依然能保持函数式的简洁优雅。
• 命令式可变状态写法仅适合极端性能场景：如果是处理超大规模数组、对运行时常数开销有极致要求，用ST monad实现可变数组、可变变量的写法确实能省掉递归参数传递的微小开销，但在绝大多数算法题、常规业务场景下，这个差异完全感知不到，没必要为了这点性能刻意切换范式。
• 选型的核心判断标准永远是逻辑清晰度：优先选你写出来最不容易出边界bug、后续维护最方便的写法即可，这类算法的核心难点是贪心规则的正确性证明，和具体用函数式还是命令式范式没有本质关联。

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