阿里330笔试思路

感觉今天做的是要凉了，事后想到了思路和大家分享一下。。。

笔试题参考https://www.nowcoder.com/discuss/396054?type=post&order=time&pos=&page=1

第一题暴力解法就是直接模拟，复杂度O(k*N), 后来用的priority queue，思路就是找每次相对的最大值，计算减量，大致和这个思路类似https://www.nowcoder.com/discuss/396025?type=post&order=time&pos=&page=1

第二题暴力解法是O(n^2), 以数组中的每个数为子序列的头计算所有其子序列的最大值统计，最后求平均。

如果继续优化需要考虑O(n)或者O(nlogn)，即每个数的处理复杂度能否进一步优化为O(1)或者O(logn)，一种简单的思路是对每个位置的数，向左和向右找其能影响到的最大范围，直至碰到边界或者比他大的数，比如 2 5 8 9 8 6 4 1 6 5，对4而言左边可以cover 0个，右边可以cover 1个，（left+1）*（right+1）就是能够以这个4为最大值的所有子序列。

如果直接这样找复杂度还是O(n^2), 我们可以考虑slding window，具体做法是queue保存index，在数字进入queue的时候，对应数组中比他小的数被弹出，直到边界或者比他大的数，这就是左边界，等到他被别的数弹出的时候就是右边界。如此复杂度为O(n)