一道数组题，如何降到小于n^2的复杂度以下

本人小白，刷这道题时只想到暴力法，请问有没有什么好办法能够降低复杂度呢？先谢谢了！

把number的数组从后往前遍历，应该可以到O(n)。

Stack 从右往左扫 stack里存的是 最大值和次数 当前等于最大就最大加1 不然不变。 遍利完了以后往外POP list里放的是次数  这样o(N] 就行

千篇一律 发表于 2021-1-29 08:55
多谢，请看下下面这段代码，应该是这个思路吧，谢谢！
[mw_shl_code=python,true]def frequencyOfMaxVal ...

关键地方就在于那starting index是一维的，并不是求任意区间，所以复杂度可以做到O(n).

用一个heap可以降到nlogn，暂时想到的就是这个

kylehuang 发表于 2021-1-28 12:55
用一个heap可以降到nlogn，暂时想到的就是这个

能详细讲一讲思路嘛？谢谢！

千篇一律 发表于 2021-1-29 02:30
能详细讲一讲思路嘛？谢谢！

下面哪个兄弟应该是对的，从后往前只需要一个counter，然后每次increment的时候跟当前max比较一下

abtesting769941 发表于 2021-1-28 14:15
把number的数组从后往前遍历，应该可以到O(n)。

多谢，请看下下面这段代码，应该是这个思路吧，谢谢！

1. def frequencyOfMaxValue(numbers, q):
   
2.   lis = []
   
3.   ans = []
   
4.   maxCount = 0
   
5.   maxValue = -pow(2,31)
   
6.   for i in range(len(numbers) - 1, -1, -1):
   
7.     if numbers[i] == maxValue:
   
8.       maxCount += 1
   
9.     elif numbers[i] > maxValue:
   
10.       maxValue = numbers[i]
    
11.       maxCount = 1
    
12.     lis.append(maxCount)
    
13.   
    
14.   lis = lis[::-1]
    
15. 
    
16.   for i in range(len(q)):
    
17.     ans.append(lis[q[i] - 1])
    
18. 
    
19.   return ans

复制代码

kylehuang 发表于 2021-1-28 14:20
下面哪个兄弟应该是对的，从后往前只需要一个counter，然后每次increment的时候跟当前max比较一下

多谢，我按照这个思路写了一段代码，不知道对不对