如何在给定数组中的任何子阵列（任何大小）中找到最大值（或最小值）？

We are given an array and some queries. Each query contains two numbers i and j. We need to find the maximum(or minimum) element in the subarray starting from index i and ending at index j in the given array.

我们得到一个数组和一些查询。每个查询包含两个数字i和j。我们需要在索引i开始并在给定数组中以索引j结束的子阵列中找到最大(或最小)元素。

For Eg.

arr = [2 , 3 , 5,  8 , 4 , 9]

and

query 1: (2 , 4)

The subarray corresponding to this query will be [5 , 8 , 4]. So, the maximum will be 8.

对应于该查询的子阵列将是[5,8,4]。所以,最大值为8。

Note: Number of queries is about 10^5 and there are about 10^6 elements in the array. Also the time limit for the execution of the program is 1s . So, I guess a solution is needed which has complexity of O(log n) or less per query, where n is the number of elements in the array.

注意:查询数量约为10 ^ 5,数组中大约有10 ^ 6个元素。此外,执行程序的时间限制为1秒。所以,我想需要一个解决方案,每个查询的复杂度为O(log n)或更少,其中n是数组中元素的数量。

5 个解决方案

#1

counter = i-1
max = MIN_INTEGER
min = MAX_INTEGER
while counter < j:
  if arr[counter] > max:
    max = arr[counter]
  if arr[counter] < min:
    min = arr[counter]
  counter++
return max,min

Edit:

Alternatively, insert it into a maxheap and minheap (O(n)), and thereafter the queries would all be O(1).

或者,将其插入maxheap和minheap(O(n)),然后查询将全部为O(1)。

#2

To elaborate Yeldar's RSQ idea, and assuming you only need to find maxima (otherwise, repeat this structure for minima as well): -You already have the value for each entry. Now break your array into pairs, and store the maximum value of each pair. (So in your example you'd get 3,8,9). Then break those into pairs (of 4 original entries) and store the maximum of that (so 8,9; the odd one out stays by itself). Repeat until you're down to a single pair, giving you the maximum of the entire array. Thus, you have multiple levels of a tree, each corresponding to a subarray.

要详细说明Yeldar的RSQ想法,并假设您只需要找到最大值(否则,也为最小值重复此结构): - 您已经拥有每个条目的值。现在将数组分成对,并存储每对的最大值。 (所以在你的例子中你得到3,8,9)。然后将它们分成两对(4个原始条目)并存储其中的最大值(因此8,9;奇数一个单独保留)。重复直到你完成一对,给你最大的整个数组。因此,您有一个树的多个级别,每个级别对应一个子阵列。

-Now, you can use this tree to find each maximum more efficiently: If you need to find the maximum from i to j, find the smallest subarray in the tree that entirely contains the range from i to j. Now you can see (from your tree) the maximum of that subarray, so trace it down (since the subarray each higher level is made up of the subarrays of two lower levels) until you get something either entirely contained in the range from i to j, or entirely disjoint. As you trace, keep track of the maximum of each path you don't take.

- 现在,您可以使用此树更有效地找到每个最大值:如果您需要找到从i到j的最大值,请在树中找到完全包含从i到j的范围的最小子阵列。现在你可以看到(从你的树上)该子阵列的最大值,因此追踪它(因为每个更高级别的子阵列由两个较低级别的子阵列组成),直到你得到的东西完全包含在从i到i的范围内j,或完全不相交。在跟踪时,跟踪您不采用的每条路径的最大值。

If it's entirely contained, you have your answer (the maximum of that range). If it's entirely disjoint, then it's not your answer (it comes from something not in the range), so take the highest maximum from the path you didn't take and repeat the process (adding in any new untaken paths), until your maximum does end up being from a subarray entirely contained in the range.

如果它完全被包含,你有答案(该范围的最大值)。如果它完全不相交,那么它不是你的答案(它来自不在范围内的东西),所以从你没有采取的路径中取出最高的最大值并重复这个过程(添加任何新的未经修改的路径),直到你的最大值最终来自完全包含在范围内的子阵列。

#3

You can try to store the maximum and minimum for the initial input by iterating through all the elements and for the next input if i and j contains the previous input then you can save time by using the previous result.

您可以尝试通过迭代所有元素来存储初始输入的最大值和最小值,如果i和j包含上一个输入,则可以尝试使用前一个结果来节省时间。

#4

Can use STL:max_element

可以使用STL:max_element

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    std::vector<int> v{2,3,5,8,4,9};
    int initial , end;
    cin>>initial>>end;
    cout <<*(std::max_element(v.begin()+initial,v.begin()+end));
    return 0;

}

other way will only work in c++17

其他方式只适用于c ++ 17

http://coliru.stacked-crooked.com/view?id=3de476681d9e1374

#include <iostream>
#include <algorithm>
#include <experimental/array>
using namespace std;

int main()
{
    decltype(auto) v = std::experimental::make_array(2,3,5,8,4,9);
    int initial=2,end=4;
    cout <<*(std::max_element(v.begin()+initial,v.begin()+end));
    return 0;

}

#5

You can use C++ STL (this is a modification of previously stated solution. We need to add +1 at the end. Because it takes index in the range [start, end). Hope this helps. Try this problem for better understanding. https://www.hackerrank.com/challenges/service-lane/problem

你可以使用C ++ STL(这是对前面提到的解决方案的修改。我们需要在结尾添加+1。因为它在[start,end]范围内需要索引。希望这可以帮助。尝试这个问题以便更好地理解。 https://www.hackerrank.com/challenges/service-lane/problem

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> arr{2,3,5,8,4,9};
    int i; // start index
    int j; // end index
    cin >> i >> j;
    cout << *max_element(arr.begin()+i, arr.begin()+j+1);

    return 0;
}

#1

counter = i-1
max = MIN_INTEGER
min = MAX_INTEGER
while counter < j:
  if arr[counter] > max:
    max = arr[counter]
  if arr[counter] < min:
    min = arr[counter]
  counter++
return max,min