区间求最大值

[qjkobe]

有大量数据存在于一段区间（不会变动）。我们需要不断查询这些数据，请你设计出一种算法。可以求出任意区间[l,r]（包含于最大区间）之间的最大值。
查询复杂度要求为O(1)

[qjkobe]

    static int[][] preST(int[] a, int len) {
        int f[][] = new int[len + 1][len + 1];
        //f[i][j]表示i位起2^j个数中的最大或最小数
        //f[i][j]的区间是[i,i+2^j)
        for (int i = 1; i <= len; i++) {
            f[i][0] = a[i];
        }
        //把f[i][j]拆分成f[i][j-1]和f[i+2^(j-1)][j-1]。这两段是相等大小的
        //f[i][j]的最大值就是这两个中最大的
        //1<<i就是2^i次方
        //为了让i,j不越界。那么
        //j不能超过log(len)。因为2^j如果超过len就必然越界。
        //i+(2^j)-1不能超过len，因为区间就是[i,i+2^j-1]
        for (int j = 1; j <= Math.log(len); j++) {
            for (int i = 1; i + (1 << j) - 1 <= len; i++) {
                f[i][j] = Math.max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
            }
        }
        return f;
    }

    static int getMax(int l, int r, int[][] f) {
        //预处理很难覆盖所有的[l,r]，但是我们可以用两个f来覆盖。
        //确定一个长度2^k，k=log(r-l+1)这个长度一定是小于等于r-l+1，因为k向下取整
        //然后以l为起始点，向右查询，f[l][k]，再以r结束，向左查询，f[r-2^k+1][k]
        //f[r-2^k+1][k]区间是[r-2^k+1,r]。+1是为了让结束处正好是r
        int k = (int) Math.log(r - l + 1);
        return Math.max(f[l][k], f[r - (1 << k) + 1][k]);
    }

    public static void main(String[] args) {
        int len = 9;
        int a[] = {-1, 1, 2, 3, 4, 5, 6, 7, 6, 5};
        //方便起见，第一位我们舍弃。
        int[][] f = preST(a, len);
        System.out.println(getMax(1, 9, f));
        System.out.println(getMax(1, 3, f));
        System.out.println(getMax(2, 5, f));
        System.out.println(getMax(3, 5, f));
        System.out.println(getMax(7, 8, f));

    }