airbnb DownSequence O(nlogn) solution

ghost11052

看到版上有人找这题的答案。写了一个O(nlogn)的解法。不知道有没有O(n)的解法，感觉可能有。我的解法也算是抛砖引玉吧。希望有帮助。第一次发题解，如有错误，请指正。
另外求加米。

您好！
本帖隐藏的内容需要积分高于 135 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

补充内容 (2019-1-12 06:22):
抱歉，这个解没有考虑到重复值。我从新贴了一个解法考虑了重复值。谢谢AppleLeung发现这个错误。

ghost11052

另外，不知道为啥粘贴的时候，a[i] 都换成了 a, 你要运行的话，记得换回来。

AppleLeung

楼主确定这个是nlogn？中间count的时候不是两个loop么

ghost11052

count部分应该是O(n). 虽然有两个循环，内循环的变量是单调递增的。也就是说，对特定的外循环值，内循环不会从 0 从新开始。
路过看过，加个米吧。有些帖子还看不了。

AppleLeung

ghost11052 发表于 2019-1-11 21:08
count部分应该是O(n). 虽然有两个循环，内循环的变量是单调递增的。也就是说，对特定的外循环值，内循环不 ...

楼主这个题你觉得怎么5331这种case算几个？

ghost11052

原来贴的解法没有考虑到重复值。你说的5331这种按照题意应该是算2个。

我从新贴一下修改过的解法在下面。很抱歉。

您好！
本帖隐藏的内容需要积分高于 135 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式