Coursera OA新题09/21

我的思路：用一个queue记录当前还没找到折扣的数，初始化就是第一个数。于是可以知道，这个队列里面的数必然不递减，否则就已经有数找到折扣，就可以出队了。然后每次遇到一个新的数，把比这个数大的数都出队，然后把这个数加入到队列。复杂度O(n). 思路是先给O(n^2)的方法，然后再优化。

sauceforge 发表于 2016-9-26 15:16
我的思路：用一个queue记录当前还没找到折扣的数，初始化就是第一个数。于是可以知道，这个队列里面的数必 ...

思路赞一个,不过我觉得应该用stack吧

liweiz1 发表于 2016-9-28 07:06
思路赞一个,不过我觉得应该用stack吧

应该是queue，因为要先进先出，每遇到一个新的数，就从后面开始把大于它的全部pop出去。