【题目描述】
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的参数,代表每个结点的最小值。
【参考答案】