算法：对于数组中的每个元素，找出在其左侧的最大价值和小于本身

Question

例如，给定一个数组：

[1, 2, 5, 4, 2, 6, 7, 3] 

找出每个元素的最大价值在其左侧和（如果不存在这种元素，则为-1）：

[-1,1, 2, 2, 1, 5, 6, 2] 

什么是最佳算法？有没有比O(n*log(n))更好的算法？

Answer 1

Bruteforce算法迭代数组，并逐一搜索访问元素，并与当前元素进行比较。因此这是O(n^2)算法。

加快此过程的关键是搜索部分。我们必须充分利用已知的已知的，这是我们访问过的元素。

那么基本的算法是这样的：

magic = new magic_data_structure 
result = [] 
for x in input_array: 
    y = magic.find_largest_but_less_than_current(x) 
    result.push(y) 
    magic.inesrt(x) 

因此，我们需要具有插入和搜索的复杂性O(logn)的数据结构。这通常是一个平衡的搜索树。我们可以使用红黑树。

为了简单起见，我们可以使用C++ stl中的set。有关更多详细信息，请参阅以下代码

例如链接：http://ideone.com/5OIBCp

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

using vi = vector <int>; 

set <int> s; 

vi foo(vi const &a) { 
    vi ret; 
    s.clear(); 
    for (auto const x: a) { 
     auto it = s.lower_bound(x); 
     if (it != begin(s)) { 
      it = prev(it); 
      ret.push_back(*it); 
     } else { 
      ret.push_back(-1); 
     } 
     s.insert(x); 
    } 
    return ret; 
} 

int main() { 
    vi a = {1, 2, 5, 4, 2, 6, 7, 3}; 
    vi b = foo(a); 
    for (auto x: b) printf("%d ", x); puts(""); 
    return 0; 
} 

---

https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree