题目链接：http://codeforces.com/problemset/problem/602/B

 

题意：

给你一个相邻数差不超过 1 的序列，求最长子串的长度，满足子串中的最大值减最小值也不超过 1。

 

思路：

区间最大值，区间最小值分别用ST表去维护就可以了，然后之后去二分答案就好了

 

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <math.h>
 6 #include <set>
 7 #include <vector>
 8 #include <stack>
 9  
10 using namespace std;
11 const int maxn= 1e5 + 10;
12  
13 int n;
14 int arr[maxn];
15 int dp[maxn][100];
16 int dp1[maxn][100];
17  
18 int Min(int l,int r){
19     int k = log(r-l+1)/log(2);
20     return  min(dp[l][k],dp[r-(1<<k)+1][k]);
21 }
22  
23 int Max(int l,int r){
24     int k = log(r-l+1)/log(2);
25     return  max(dp1[l][k],dp1[r-(1<<k)+1][k]);
26 }
27  
28 bool check(int x){
29     for (int i=1;i+x-1<=n;i++){
30         if (Max(i,i+x-1)-Min(i,i+x-1)<=1)
31             return true;
32     }
33     return false;
34 }
35  
36 int main(){
37     scanf("%d",&n);
38     for (int i=1;i<=n;i++){
39         scanf("%d",&arr[i]);
40     }
41     for (int i=1;i<=n;i++){
42         dp[i][0] = arr[i];
43         dp1[i][0] = arr[i];
44     }
45     for (int j=1;(1<<j)<=n;j++){
46         for (int i=1;i+(1<<j)-1<=n;i++){
47             dp[i][j] = min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
48             dp1[i][j] = max(dp1[i][j-1],dp1[i+(1<<(j-1))][j-1]);
49         }
50     }
51     int l=1,r=n+1,mid;
52     int len = 1;
53     while (l<=r){
54         mid = (l+r)/2;
55         if (check(mid)){
56             len = max(mid,len);
57             l = mid + 1;
58         }
59         else{
60             r = mid-1;
61         }
62     }
63     printf("%d\n",len);
64     return 0;
65 }