寻找更快的解决方案

我在这个问题上苦苦挣扎了3天,几乎快要放弃了。

我有N个房屋的阵列(排列),每座房屋都有高度。我也有一个数字P,飞机的数量。

当飞机经过房屋时,如果arr [i]> arr [i + 1]并且arr [i]> arr [i-1](房屋比其邻居高),飞机会摧毁它,从而减少arr [ i] = 0。 我必须归还P架飞机经过后摧毁的房屋数量。

使用O(NP)解决方案确实很容易,但是问题是...太慢了。我必须比O(NP)快。您能给我这个问题的线索或建议吗?

这里有些例子:

输入:

10 2

4 1 3 2 4 5 3 1 2 1

输出:8

输入:

4 10

1 3 3 4

输出:1

评论