双指针算法：原理、应用与性能优化

1. 双指针算法的本质与应用场景

双指针算法（Two Pointers Technique）是算法领域中一种经典且高效的解题思路，特别适合处理线性数据结构中的序列问题。这种算法的核心在于通过维护两个指针（索引）在序列中按特定规律移动，从而将原本O(n²)的时间复杂度优化到O(n)级别。

在实际工程中，双指针算法最常见的应用场景包括：

• 有序数组的查找与合并
• 滑动窗口类问题
• 链表中的环检测与相交判断
• 字符串的匹配与回文判断
• 容器盛水问题等极值计算

提示：双指针并非真正的指针实现，在Python等语言中通常用整数索引模拟指针行为，而在C++中可以直接使用指针变量。

2. 单调性在双指针中的关键作用

2.1 单调性的数学定义

单调性（Monotonicity）是指序列元素按照严格递增或递减的规律排列的特性。在双指针算法中利用单调性，可以确保指针移动方向的确定性，避免回溯操作带来的性能损耗。

典型的单调性应用案例：

python复制# 有序数组的两数之和
def two_sum(nums, target):
    left, right = 0, len(nums)-1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return [left, right]
        elif s < target:
            left += 1  # 利用递增单调性，左指针只能右移
        else:
            right -= 1  # 右指针只能左移

2.2 单调性与指针移动的关联规则

当序列具有单调性时，双指针的移动遵循以下黄金法则：

1. 当条件满足时，一个指针固定移动（如右指针左移）
2. 当条件不满足时，另一个指针补偿移动（如左指针右移）
3. 移动方向必须与单调性方向一致

这种策略确保了每个元素最多被访问两次，将时间复杂度从暴力解的O(n²)降至O(n)。

3. 八大经典单调性双指针问题解析

3.1 盛最多水的容器（LeetCode 11）

python复制def maxArea(height):
    left, right = 0, len(height)-1
    max_area = 0
    while left < right:
        h = min(height[left], height[right])
        max_area = max(max_area, h*(right-left))
        if height[left] < height[right]:
            left += 1  # 保持较高边界不动
        else: