一、双指针简介

双指针是一种简单而又灵活的技巧和思想，单独使用可以轻松解决一些特定问题，和其他算法结合也能发挥多样的用处。

双指针算法是一种通过设置两个指针不断进行单向移动来解决问题的算法。
它包含两种形式：

1. 两个指针分别指向不同的序列。比如：归并排序的合并过程。
2. 两个指针指向同一个序列。比如：快速排序的划分过程。

一般更多使用、也更难想到的是第2种情况。

原本两个指针是有 种组合，因此时间复杂度是 。
而双指针算法就是运用单调性使得指针只能单向移动，因此总的时间复杂度只有 ，也就是

for (int i = 0, j = 0; i < n; i++)
{
    while (j < i && check(i, j)) j++;
    // 每道题目的具体逻辑
}

典型例题：

1.排列排序

https://www.luogu.com.cn/problem/P7714
尺取法的经典应用

2.天气预报

https://ac.nowcoder.com/acm/contest/30532/G
来自上海理工大学GPLT 2022校内选拔赛