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);
}
}