有n(n>0)个元素的正整型数组a，打印每个数组元素前面值比他小并且下标最大的元素，如果没有则打印-1，请使用尽可能高效的方法来实现。举例：数组a为[3,6,1,4,2,3,7,5,8], 则打印[-1,3,-1,1,1,2,3,3,5]。大家有没有比O（n2）（就是遍历数组，再遍历当前数的前面值的方法）更好的方法啊？

个人还是比价喜欢360 公司的技术氛围的，但周围没有人在360工作，所以不知道牛客网有没有学长学姐可以内推下，谢谢。