给定一个整数数组（下标由 0 到 n-1，其中 n 表示数组的规模），以及一个查询列表。每一个查询列表有两个整数
[start, end]。 对于每个查询，计算出数组中从下标 start 到 end 之间的数的最小值，并返回在结果列表中。
注意事项
样例
对于数组
[1,2,7,8,5]， 查询[(1,2),(0,4),(2,4)]，返回[2,1,5]
挑战
每次查询在O(logN)的时间内完成
代码
- 无需考虑拆分区间
/**
* Definition of Interval:
* public class Interval {
* int start, end;
* Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
* }
*/
public class Solution {
/*
* @param A: An integer array
* @param queries: An query list
* @return: The result list
*/
class SegmentTreeNode {
public int start;
public int end;
public int min;
SegmentTreeNode left;
SegmentTreeNode right;
public SegmentTreeNode(int start, int end, int min) {
this.start = start;
this.end = end;
this.min = min;
this.left = null;
this.right = null;
}
}
public SegmentTreeNode build(int start, int end, int[] A) {
if (start > end) {
return null;
}
if (start == end) {
return new SegmentTreeNode(start, end, A[start]);
}
SegmentTreeNode root = new SegmentTreeNode(start, end, A[0]);
int mid = start + (end - start) / 2;
root.left = build(start, mid, A);
root.right = build(mid + 1, end, A);
root.min = Math.min(root.left.min, root.right.min);
return root;
}
public int query(SegmentTreeNode root, int start, int end) {
if (start <= root.start && end >= root.end) {
return root.min;
}
int mid = root.start + (root.end - root.start) / 2;
int ans = Integer.MAX_VALUE;
if (start <= mid) {
ans = Math.min(ans, query(root.left, start, end));
}
if (end > mid) {
ans = Math.min(ans, query(root.right, start, end));
}
return ans;
}
SegmentTreeNode root;
public List<Integer> intervalMinNumber(int[] A, List<Interval> queries) {
root = build(0, A.length - 1, A);
List<Integer> list = new ArrayList<>();
for (Interval num : queries) {
int res = query(root, num.start, num.end);
list.add(res);
}
return list;
}
}
- 手动拆分区间
class SegmentTreeNode {
public int start, end, min;
public SegmentTreeNode left, right;
public SegmentTreeNode(int start, int end, int min) {
this.start = start;
this.end = end;
this.min = min;
this.left = this.right = null;
}
}
public class Solution {
/**
*@param A, queries: Given an integer array and an query list
*@return: The result list
*/
public SegmentTreeNode build(int start, int end, int[] A) {
// write your code here
if(start > end) { // check core case
return null;
}
SegmentTreeNode root = new SegmentTreeNode(start, end, Integer.MAX_VALUE);
if(start != end) {
int mid = (start + end) / 2;
root.left = build(start, mid, A);
root.right = build(mid+1, end, A);
root.min = Math.min(root.left.min, root.right.min);
} else {
root.min = A[start];
}
return root;
}
public int query(SegmentTreeNode root, int start, int end) {
// write your code here
if(start == root.start && root.end == end) { // 相等
return root.min;
}
int mid = (root.start + root.end)/2;
int leftmin = Integer.MAX_VALUE, rightmin = Integer.MAX_VALUE;
// 左子区
if(start <= mid) {
if( mid < end) { // 分裂
leftmin = query(root.left, start, mid);
} else { // 包含
leftmin = query(root.left, start, end);
}
}
// 右子区
if(mid < end) { // 分裂 3
if(start <= mid) {
rightmin = query(root.right, mid+1, end);
} else { // 包含
rightmin = query(root.right, start, end);
}
}
// else 就是不相交
return Math.min(leftmin, rightmin);
}
public List<Integer> intervalMinNumber(int[] A,
List<Interval> queries) {
// write your code here
SegmentTreeNode root = build(0, A.length - 1, A);
List<Integer> ans = new ArrayList<Integer>();
for(Interval in : queries) {
ans.add(query(root, in.start, in.end));
}
return ans;
}
}
