在数组中查找未来最高值的算法
在数组中查找未来最高值的算法
提问于 2020-07-04 03:30:39
我正在解决hackerrank中的一个问题，为此，我需要解决一个子问题。给定一个数组，我需要填充另一个数组来填充所有未来的高点。举例说明
arr1 = [5,2,4,1,4,7,2,4,3]
output: [true, true, true, true, true, false, true, false, false]在索引0处，5的未来峰值为7。同样的方式，2的未来高点为4，4的未来高点为7，依此类推，我能够使用泛洪填充技术计算出未来的峰值，这意味着由于第一个元素5的未来峰值为7，因此中间的所有项都可以用true填充。
但是，这仍然不是O(N)，因为考虑到这个数组
arr2 = [8,7,6,5,4,3,2,1]
output: [false, false .... false]我的泛洪填充技术在这种情况下将消耗O(N²)，因为这里没有泛洪填充。泛洪填充仍然比蛮力更好，但我需要最优的算法。
我想知道O(N)是否对所有情况都是可能的？
回答 1
Stack Overflow用户
回答已采纳
发布于 2020-07-04 03:39:20
这可以在O(n)中完成。
#include <iostream>
using namespace std;
int main(){
int n = 9;
int arr[] = {5,2,4,1,4,7,2,4,3};
int fut[] = {0,0,0,0,0,0,0,0,0};
int maxAfter = arr[n - 1];
for(int i = n - 2; i >= 0; i--){
if(arr[i] < maxAfter) fut[i] = 1;
else maxAfter = arr[i];
}
for(int i = 0; i < n; i++) cout<<fut[i]<<" ";
}从数组的末尾开始，返回到开始处，总是存储找到的最大值，这个值将用来表示是否有人比您当前正在查找的索引中的值更大。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/62721671
复制相关文章
相似问题
腾讯云开发者
