205-区间最小数
思路
这里需要用上 lintcode-201-线段树的构造 和 lintcode-202-线段树的查询，不过需要注意的是，这里求得是最小值，所以需要将线段树代码略作修改，原先 SegmentTreeNode 类中的 max 现在表示的是在区间 [start, end] 的最小元素值
code
/**
* Definition of Interval:
* class Interval{
* int start, end;
* Interval(int start, int end) {
* this->start = start;
* this->end = end;
* }
* };
*/
class Solution {
public:
/**
*@param A, queries: Given an integer array and an query list
*@return: The result list
*/
vector<int> intervalMinNumber(vector<int> &A, vector<Interval> &queries) {
// write your code here
if (A.empty() || queries.empty()) {
return vector<int>();
}
vector<int> result;
SegmentTreeNode * root = build(0, A.size() - 1, A);
for (int i = 0; i < queries.size(); i++) {
result.push_back(query(root, queries[i].start, queries[i].end));
}
return result;
}
SegmentTreeNode * build(int start, int end, vector<int> &nums) {
// write your code here
if (start > end) {
return nullptr;
}
SegmentTreeNode *root = new SegmentTreeNode(start, end, 0);
if (start != end) {
root->left = build(start, (start + end) / 2, nums);
root->right = build((start + end) / 2 + 1, end, nums);
root->max = min(root->left->max, root->right->max);
}
else {
root->max = nums[start];
}
return root;
}
int query(SegmentTreeNode *root, int start, int end) {
// write your code here
int mid = (root->start + root->end) / 2;
if (start <= root->start && end >= root->end) {
return root->max;
}
else if (mid < start) {
return query(root->right, start, end);
}
else if (mid + 1 > end) {
return query(root->left, start, end);
}
else {
return min(query(root->left, start, mid), query(root->right, mid + 1, end));
}
}
};