Interval Minimum Number 205

Question

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

Solution

水题，就是将build tree和query minimum结合起来求一连串的query而已。

代码如下：

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

public class Solution {
    /**
     *@param A, queries: Given an integer array and an query list
     *@return: The result list
     */
    public ArrayList<Integer> intervalMinNumber(int[] A, 
                                                ArrayList<Interval> queries) {
        // write your code here
        ArrayList<Integer> res = new ArrayList<Integer>();
        if(A == null || A.length == 0 || queries == null || queries.size() == 0){
            return res;
        }

        SegmentTreeNode root = SegmentTreeBuilder(A, 0, A.length - 1);

        for(int i = 0; i < queries.size(); i++){
            int min = query(root, queries.get(i).start, queries.get(i).end);
            res.add(min);
        }

        return res;
    }

    private SegmentTreeNode SegmentTreeBuilder(int[] A, int start, int end){
        if(start == end){
            return new SegmentTreeNode(start, end, A[start]);
        }

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

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

        return root;
    }

    public int query(SegmentTreeNode root, int start, int end) {
        // write your code here
        if(root == null || start > end || start > root.end || end < root.start){
            return -1;
        }

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

        int mid = (root.start + root.end) / 2;
        //跨越中点
        if(start <= mid && end >= mid + 1){
            int left = query(root.left, start, mid);
            int right = query(root.right, mid + 1, end);
            return Math.min(left, right);
        }
        //左边
        if(end <= mid){
            return query(root.left, start, end);
        }
        //右边
        return query(root.right, start, end);
    }
}