## Wednesday, May 11, 2016

### Lintcode 205 - Interval Minimum Number

http://www.cnblogs.com/EdwardLiu/p/5175033.html
```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.

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]

Note
We suggest you finish problem Segment Tree Build, Segment Tree Query and Segment Tree Modify first.

Challenge
O(logN) time for each query```
``````    public ArrayList<Integer> intervalMinNumber(int[] A,
ArrayList<Interval> queries) {
ArrayList<Integer> res = new ArrayList<Integer>();
if (A == null || queries == null) return res;
MinTreeNode root = buildTree(A, 0, A.length-1);
for (Interval i: queries) {
}
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));
}``````

```15     public class SegmentTreeNode {
16         int min;
17         int start;
18         int end;
19         SegmentTreeNode left;
20         SegmentTreeNode right;
21         public SegmentTreeNode(int start, int end) {
22             this.start = start;
23             this.end = end;
24             this.min = Integer.MAX_VALUE;
25             this.left = null;
26             this.right = null;
27         }
28     }
29
30     SegmentTreeNode root;
31
32     public ArrayList<Integer> intervalMinNumber(int[] A,
33                                                 ArrayList<Interval> queries) {
35         ArrayList<Integer> res = new ArrayList<Integer>();
36         root = buildTree(A, 0, A.length-1);
37         query(res, queries);
38         return res;
39     }
40
41     public SegmentTreeNode buildTree(int[] A, int start, int end) {
42         SegmentTreeNode cur = new SegmentTreeNode(start, end);
43         if (start == end) {
44             cur.min = A[start];
45         }
46         else {
47             int mid = (start+end)/2;
48             cur.left = buildTree(A, start, mid);
49             cur.right = buildTree(A, mid+1, end);
50             cur.min = Math.min(cur.left.min, cur.right.min);
51         }
52         return cur;
53     }
54
55     public void query(ArrayList<Integer> res, ArrayList<Interval> queries) {
56         for (Interval interval : queries) {
57             int result = queryTree(root, interval.start, interval.end);
59         }
60     }
61
62     public int queryTree(SegmentTreeNode cur, int start, int end) {
63         if (start==cur.start && end==cur.end) {
64             return cur.min;
65         }
66         int mid = (cur.start + cur.end)/2;
67         if (end <= mid) return queryTree(cur.left, start, end);
68         else if (start > mid) return queryTree(cur.right, start, end);
69         else return Math.min(queryTree(cur.left, start, mid), queryTree(cur.right, mid+1, end));
70     }
```