算法分析

• 1、固定L，遍历R

• 2、在[L,R]区域中找到最大值Max，最小值Min，若maxv - minv == j - i，则说明该区域[L,R]是递增且连续的

时间复杂度 $O(n^2)$

参考文献

算法提高课

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
    static int N = 10010;
    static int[] f = new int[N];
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine().trim());
        String[] s1 = reader.readLine().split(" ");
        for(int i = 1;i <= n;i++) f[i] = Integer.parseInt(s1[i - 1]);
        int res = 0;
        for(int i = 1;i <= n;i++)
        {
            int minv = Integer.MAX_VALUE;
            int maxv = Integer.MIN_VALUE;
            for(int j = i;j <= n;j++)
            {
                minv = Math.min(minv, f[j]);
                maxv = Math.max(maxv, f[j]);
                if(maxv - minv == j - i) res ++;
            }
        }
        System.out.println(res);
    }
}