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) { 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)); }
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); 58 res.add(result); 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 }
