怎么连续求取长数组中连续的分数据段的最值
如何连续求取长数组中连续的分数据段的最值?
RT. 假设我有一个很长的数组, 1000个元素吧.
现在我该怎么连续获取这个数组内一个个连续的小数据段的最值呢?
比如元素1~100的最值, 2~101号元素的最值, 3~102号元素的最值.
如果单纯用循环来做的话就太麻烦了...请问大家有没有什么好的思路可以减少运行时间呢?
谢谢!
------解决思路----------------------
以分段的组号为键，数组中的元素为值，(即multimap<组号,元素值>)插入到multimap中。插入结束，排序也就结束了。然后调用equal_range()就知道每组的最大和最小值了
------解决思路----------------------
求区间最值，线段树最适合了，时间复杂度O(lgN)。
RT. 假设我有一个很长的数组, 1000个元素吧.
现在我该怎么连续获取这个数组内一个个连续的小数据段的最值呢?
比如元素1~100的最值, 2~101号元素的最值, 3~102号元素的最值.
如果单纯用循环来做的话就太麻烦了...请问大家有没有什么好的思路可以减少运行时间呢?
谢谢!
------解决思路----------------------
以分段的组号为键，数组中的元素为值，(即multimap<组号,元素值>)插入到multimap中。插入结束，排序也就结束了。然后调用equal_range()就知道每组的最大和最小值了
------解决思路----------------------
求区间最值，线段树最适合了，时间复杂度O(lgN)。