两点法是通常用来求解简单的区间问题的O(n)算法，两点法顾名思义有两个点，一个起点一个终点，在区间上维护这两个点，动态更新题目要求的值的大小
这里举出NOJ两道较简单且有代表性的题，一道是数字一道是字符串
炒股票的女巫璐璐
时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte总提交:674 测试通过:40
题目描述
女巫璐璐生活在美丽的仙林。璐璐突发奇想想到了炒股。璐璐运用了她的神奇魔法获取了一支股票未来连续N天的价格。
璐璐现在想知道从这N天里，哪天买入，哪天卖出可以使自己自己的收益最大。
输入
输入第一行是一个整数T，代表测试用例个数。接下来的每组数据第一行为一个整数N(2≤N≤100000)，代表这支股票未来N天的价格，第二行为N个整数a1,a2,..aN。
输出
输出璐璐能得到的最大收益。如果璐璐无论怎么买入卖出都不能赚钱（收益大于0），输出0。
输出格式见样例，首先输出“Case #: ”，再输出答案，其中#表示第几个测试用例。
样例输入
3332131233231
样例输出
Case1:0Case2:2Case3:1
题目链接：?&method=showdetail&id=1972
题目分析：st，ed初始化为0，当a[st] < a[i]时说明是递增的，可卖出，所以更新ed和ans，否则，更新st，因为如果当前点后第二个点比当前点大，后第一个点比当前点小，显然应当把当前的后的那个点当作起点
#include <cstdio>#include <algorithm>using namespace std;int a[100005];int main(){int T;scanf("%d", &T);for(int ca = 1; ca <= T; ca++){int n, ans = 0;scanf("%d", &n);for(int i = 0; i < n; i++)scanf("%d", &a[i]);int st = 0, ed = 0;for(int i = 1; i < n; i++){if(a[st] < a[i]){ed = i;ans = max(ans, (a[ed] – a[st]));}elsest = i;}printf("Case %d: %d\n", ca, ans);}}BRN
时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte总提交:130 测试通过:36
题目描述
大学四事之娱乐生活。
Best Riven NUPT ，即南邮最强瑞文，作为一个LOSER，啊不，LOLER，，BENBB一直向着这个目标努力练习着。
作为英雄联盟中最需要操作的几个英雄之一，一个优秀的瑞文玩家，需要掌握其特殊的连招技巧！瑞文的主要技能为QWER，加上A人和鼠标右键总计6种操作命令。这里我们把鼠标右键记作1。要想有效的在与敌人的较量中获得胜利，就需要在短时间内打出更多的伤害，即取消游戏中的前摇和后摇。具体方法如下：
在使用Q技能之后用鼠标右键可以取消Q的施法后摇。
在A之后使用Q技能能取消A的后摇。
在E技能之后使用W或者R可以取消施法前摇。 ……如此一来我们定义下BRN所需要的操作吧。1、Q之后必须接上鼠标右键1。2、A之后必须接上Q技能。3、W和R之前必须是E技能。4、R和W之后必须接上Q技能或者A。5、其余技能可以随意连接
BENBB在练习中释放了很多次技能，现在请你找出其中最长的满足BRN需求的连招的长度。
输入第一行为一个正整数T，表示有T组数据每组为一行字符串（长度不超过10000，所有字母都为大写）输出每组单独一行输出一个正整数m代表最长BRN连招长度 样例输入3AQ1AQWERA1ERQ1AQ1EWAQ1111111ERA样例输出4321题目链接：?&method=showdetail&id=1974
题目分析：运用两点法，当可以连击时更新ed，不能连击时更新st
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;char s[10000];int main(){int T;scanf("%d", &T);while(T–){scanf("%s", s);int len = strlen(s);int ans = 0, st = 0, ed = 0;for(int i = 0; i < len;){ans = max(ans, ed – st + 1);if(s[i] == 'A' && s[i + 1] != 'Q' ){i ++;st = i;}else if(s[i] == 'Q' && s[i + 1] != '1' ){i ++;st = i;}else if((s[i + 1] == 'W' && s[i] != 'E')){i ++;st = i;}else if((s[i + 1] == 'R' && s[i] != 'E')){i ++;st = i;}else if(s[i] == 'R' && (s[i + 1] != 'Q' && s[i + 1] != 'A')){i ++;st = i;}else if(s[i] == 'W' && (s[i + 1] != 'Q' && s[i + 1] != 'A')){i ++;st = i;}else{i ++;ed = i;}}printf("%d\n", ans);}}
用最少的浪费面对现在
