Problem

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.

Example

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

Challenge

O(logN) time for each query

Note

这道题目是筛选出Interval数组中的最小值，存入新数组。因此，联想到Segment Tree Build和Segment Tree Query系列的题目，对于Interval的处理，使用线段树是非常有效的方法。之前我们创建的线段树，有max和count两个properties。参照max这个参数，可以考虑在这道题增加一个min的参数，代表每个结点的最小值。

Solution

public class Solution {    public ArrayList
    
      intervalMinNumber(int[] A,                                                 ArrayList
     
       queries) {        ArrayList
      
        res = new ArrayList
       
        ();        if (A == null || queries == null) return res;        MinTreeNode root = buildTree(A, 0, A.length-1);        for (Interval i: queries) {            res.add(getMin(root, i.start, i.end));        }        return res;    }    //创建新的树结构MinTreeNode    public class MinTreeNode {        int start, end, min;        MinTreeNode left, right;        public MinTreeNode(int start, int end) {            this.start = start;            this.end = end;        }        public MinTreeNode(int start, int end, int min) {            this(start, end);            this.min = min;        }    }    //创建新的MinTreeNode    public MinTreeNode buildTree(int[] A, int start, int end) {        if (start > end) return null;        //下面四行语句是recursion的主体        if (start == end) return new MinTreeNode(start, start, A[start]);        MinTreeNode root = new MinTreeNode(start, end);        root.left = buildTree(A, start, (start+end)/2);        root.right = buildTree(A, (start+end)/2+1, end);        //下面三行语句设置每个结点的min值        if (root.left == null) root.min = root.right.min;        else if (root.right == null) root.min = root.left.min;        else root.min = Math.min(root.left.min, root.right.min);        return root;    }    //获得最小值min的子程序    public int getMin(MinTreeNode root, int start, int end) {        //空集和越界情况        if (root == null || root.end < start || root.start > end) {            return Integer.MAX_VALUE;        }        //最底层条件结构        if (root.start == root.end || (start <= root.start && end >= root.end)) {            return root.min;        }        //递归        return Math.min(getMin(root.left, start, end), getMin(root.right, start, end));    }}