以盛最多水的容器问题为例探究O(n²)解法优化为O(n)算法的通用理论

本题O(n)解法的正确性根源 #

你提到的LeetCode「盛最多水的容器」问题，双指针解法能做到O(n)的核心原因是每一步操作都直接排除了一整类不可能成为最优解的组合，不需要像暴力解法那样逐个遍历所有两两组合：
容器的面积计算公式为 area = min(height[left], height[right]) * (right - left)，假设当前左指针的高度小于右指针的高度：

此时如果我们选择移动右指针，无论右指针左移后对应的新高度是多少，新的面积都不可能超过当前面积：新的左右间距变小了，且两个柱子的最小高度最多只能等于当前左指针的高度。也就是说所有以当前左指针为左边界、右指针在当前右指针左侧的组合，全部都不可能是最优解，我们可以直接把这批组合全部排除，只需要移动左指针即可。

每一轮我们都可以排除O(n)个无效组合，总共只需要移动最多n次指针就能覆盖所有可能的候选组合，因此整体时间复杂度就是O(n)。

同类问题的通用判定特征 #

这类可以从O(n²)暴力解法直接优化到O(n)的贪心/双指针问题，通常都满足三个共性：

• 问题的最优解是从n个元素中选取固定数量的元素（大多是2个）组成，朴素解法需要遍历所有对应数量的组合
• 存在可通过反证法证明的淘汰规则：每做一次O(1)成本的判断，就能直接排除一整批不可能成为最优解的组合，且不会漏过真正的最优解
• 最优解的评估维度存在单调性：比如本题的间距随着指针移动单调减小，高度的约束可以直接判定后续组合的上限

目前没有完全通用的方法只看问题定义就能100%判定可以用O(n)复杂度求解，但只要问题符合上述三个特征，就可以优先尝试双指针、贪心方向的优化，不需要死磕更高复杂度的解法。

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