注意事项

/**

 * Definition of Interval:

 * classs 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

     */

    /*

    思路1：直接调用sort函数对查询区间排序，然后将最小值存入容器；方法简单，但是时间复杂度高，超时了；

   */

    vector<int> intervalMinNumber(vector<int> &A, vector<Interval> &queries) {

        // write your code here

        vector<int> res;

        if(queries.size()==0){

            return res;

        }

        vector<int> temp;

        for(int i=0;i<queries.size();i++){

            for(int k=queries[i].start;k<=queries[i].end;k++ ){

                temp.push_back(A[k]);

            }

            sort(temp.begin(),temp.end());

            res.push_back(temp[0]);

            temp.clear();

        }

        return res;

    }

 }

/**

 * Definition of Interval:

 * classs Interval {

 *     int start, end;

 *     Interval(int start, int end) {

 *         this->start = start;

 *         this->end = end;

 *     }

 */

class SegmentTreeNode22 {

public:

    int start, end, min;

    SegmentTreeNode22* left, *right;

    SegmentTreeNode22(int start, int end) {

        this->start = start;

        this->end = end;

        this->min = 0;

        this->left = this->right = NULL;

    }

};

class Solution {

public:

    /**

     *@param A, queries: Given an integer array and an query list

     *@return: The result list

     */

    /*思路2：构建线段树，构建方法参考线段树构造||;

           然后利用线段树的特殊性质进行查询;

           这道题目很经典，包含了线段树的构造，查询，一定要会！

    /*

    //构建线段树;

    SegmentTreeNode22* build(int start, int end, vector<int>& A) {  

        if(start > end) {

            return NULL;

        }  

        SegmentTreeNode22* root = new SegmentTreeNode22(start, end);  

        if(start != end) {

            int mid = (start + end) / 2;

            root->left = build(start, mid, A);

            root->right = build(mid+1, end, A);

            root->min = min(root->left->min, root->right->min);

        } else {

            root->min = A[start];

        }

        return root;

    }  

    //线段树查询

    int query(SegmentTreeNode22* root, int start, int end) {  

        if(start <= root->start && root->end <= end) {

            return root->min;

        }  

        int mid = (root->start + root->end)/2;  

        if(start>mid)

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

    }  

    vector<int> intervalMinNumber(vector<int> &A, vector<Interval> &queries) {

        SegmentTreeNode22* root = build(0, A.size()- 1, A);//构造线段树；

        vector<int> res;

        for(Interval qujian : queries) {

            res.push_back(query(root, qujian.start, qujian.end));

        }

        return res;

    }

};