Lintcode205 Interval Minimum Number solution 题解
发布在LINTCODE2018年2月7日view:427移动开发
在文章任何区域双击击即可给文章添加【评注】!浮到评注点上可以查看详情。

【题目描述】

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.

Notice:We suggest you finish problem Segment Tree Build,Segment Tree Query and  Segment Tree Modify first.

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

【注】:在做此题前,建议先完成以下三道题线段树的构造,线段树的查询及线段树的修改。

【题目链接】

www.lintcode.com/en/problem/interval-minimum-number/

【题目解析】

这道题目是筛选出Interval数组中的最小值,存入新数组。因此,联想到Segment Tree Build和Segment Tree Query系列的题目,对于Interval的处理,使用线段树是非常有效的方法。之前我们创建的线段树,有max和count两个properties。参照max这个参数,可以考虑在这道题增加一个min的参数,代表每个结点的最小值。

【参考答案】

www.jiuzhang.com/solutions/interval-minimum-number/

评论
发表评论
暂无评论
WRITTEN BY
PUBLISHED IN

我的收藏