lintcode205. 区间最小数线段树

蔚落 2023-07-06 13:27 12阅读 0赞

给定一个整数数组（下标由 0 到 n-1，其中 n 表示数组的规模），以及一个查询列表。每一个查询列表有两个整数 \[start, end\]。 对于每个查询，计算出数组中从下标 start 到 end 之间的数的最小值，并返回在结果列表中。

样例
    样例1：
    输入：数组 ：[1,2,7,8,5] 查询 ：[(1,2),(0,4),(2,4)]。输出：[2,1,5]
    样例2：
    输入：数组 ：[4,5,7,1] 查询 ：[(1,2),(1,3)]。输出：[5,1]
    
    挑战
    每次查询在O(logN)的时间内完成
    
    注意事项
    在做此题前，建议先完成以下三道题 线段树的构造， 线段树的查询 及 线段树的修改。

自己写了一个线段树的类，一直提示重定义了，删去以后就accpeted了  
最好先看过  
线段树的构造： https://blog.csdn.net/weixin\_43981315/article/details/104364314  
线段树的查询：https://blog.csdn.net/weixin\_43981315/article/details/104199741

思路：里面的线段树只有最大值，没有最小值，所以需要我们稍微修改一下，每一次取左右子树的最大值中的较小值即可。

/**
     * Definition of Interval:
     * classs Interval {
     *     int start, end;
     *     Interval(int start, int end) {
     *         this->start = start;
     *         this->end = end;
     *     }
     * }
     */
    /*class SegmentTreeNode
    {
    public:
        int start;
        int end;
        int min;
        SegmentTreeNode *left, *right;
        SegmentTreeNode(int start,int end,int min)
        {
            this->start=start;
            this->end=end;
            this->min=min;
            this->left = this->right = NULL;
        }
    };*/
    class Solution {
        
    public:
        /**
         * @param A: An integer array
         * @param queries: An query list
         * @return: The result list
         */
        vector<int> intervalMinNumber(vector<int> &A, vector<Interval> &queries) {
        
            // write your code here
            vector<int> res;
            if(A.size()<=0||queries.size()<=0) return res;
            SegmentTreeNode*root=build(A,0,A.size()-1);
            for (int i = 0; i < queries.size(); i++) {
        
                res.push_back(query(root,queries[i].start,queries[i].end));
            }
            return res;
        }
        SegmentTreeNode*build(vector<int>&A,int start,int end)
        {
        
            SegmentTreeNode*node;
            if(start!=end)
                node=new SegmentTreeNode(start,end,0);
            else
                node=new SegmentTreeNode(start,end,A[start]);
            if(start==end) return node;
            node->left=build(A,start,(start+end)/2);
            node->right=build(A,(start+end)/2+1,end);
            node->max=min(node->left->max,node->right->max);
            return node;
        }
        int query(SegmentTreeNode * root, int start, int end) {
        
            // write your code here
            int mid=(root->start+root->end)/2;
            if(root->start>=start&&root->end<=end) return root->max;
            else if(start>mid)return query(root->right,start,end);
            else if(end<mid+1)return  query(root->left,start,end);
            else return min(query(root->left,start,end),query(root->right,start,end));
        }
    };