Given an integer array (index from 0 to n-1, where n is the size of this array), and an query list. Each query has two integers[start, end]. For each query, calculate the minimum number between index start and end in the given array, return the result list.

Notice

We suggest you finish problemSegment Tree Build,Segment Tree QueryandSegment Tree Modifyfirst.

Have you met this question in a real interview?

Yes

Example

For array[1,2,7,8,5], and queries[(1,2),(0,4),(2,4)], return[2,1,5]

线段树求解， O(klogn)

/**
 * Definition of Interval:
 * public class Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 * }
 */
class SegmentTree {
    int start, end, min;
    SegmentTree left, right;
    public SegmentTree(int start, int end, int min) {
        this.start = start;
        this.end = end;
        this.min = min;
        this.left = this.right = null;
    }
}

public class Solution {
    /*
     * @param A: An integer array
     * @param queries: An query list
     * @return: The result list
     */

    public SegmentTree build(int[] A, int start, int end) {
        if (start == end) {
            return new SegmentTree(start, start, A[start]);
        }

        SegmentTree root = new SegmentTree(start, end, 0);
        int mid = (start + end) / 2;
        SegmentTree left = build(A, start, mid);
        SegmentTree right = build(A, mid + 1, end);

        root.left = left;
        root.right = right;
        root.min = Math.min(left.min, right.min);
        return root;
    } 

    public int query(SegmentTree root, int start, int end) {
        if (root == null) {
            return 0;
        }

        if (root.start >= start && root.end <= end) {
            return root.min;
        }

        int mid = (root.start + root.end) / 2;
        if (end <= mid) {
            return query(root.left, start, end);
        } else if (start > mid) {
            return query(root.right, start, end);
        }

        return Math.min(query(root.left, start, mid), query(root.right, mid + 1, end));
    }

    public List<Integer> intervalMinNumber(int[] A, List<Interval> queries) {
        // write your code here
        List<Integer> ans = new ArrayList<>();
        if (A == null || A.length == 0 || queries == null || queries.size() == 0) {
            return ans; 
        }

        SegmentTree root = build(A, 0, A.length - 1);
        // System.out.println(query(root, 0, 1));
        // System.out.println(query(root, 2, 2));
        for (Interval inter : queries) {
            ans.add(query(root, inter.start, inter.end));
        }
        return ans;
    }
}