对时间复杂度要求很高的一道看似简单的题。。。

输入数据是List<Data>。List中有n个数据；Data的数据结构是class Data {String result; long time}。其中result只有两种，"Win"和"Lose"。要根据time找到最后一次数据result更替。result更替就是时间上相邻的两个数据result从Win到Lose或者从Lose到Win。


比如t1:Win, t2:Win, t3:Win, t4:Lose, t5:Lose, t6:Lose, 则结果为t4:Lose。
注意数据可能是乱序的，比如t5:Lose, t6:Lose, t4:Lose, t1:Win, t2:Win, t3:Win, 但是结果依然要是t4:Lose。
如果是t1:Win, t2:Lose; t3:Win, t4:Lose则结果是t4:Lose
如果是t4:Lose, t1:Win, t3:Lose, t2:Win则结果是t3:Lose //因为t3是最后一次result更替


time是unbounded，也就是任意时间。
t1, t2, t3代表时间排序后的顺序。但是实际数据中可以是任意顺序。


要求时间复杂度是O(n)！！也就是说排序基本被排除。time是unbounded所以桶排序也没戏了。。。


大神们有什么好想法吗？

过一遍，找到最晚出现的Win和Lose，这是O(N)。

假设Win和Lose都有，否则无解。

不妨假设最晚的Win比Lose早，则需求的点就是这个Win后面那个Lose，再过一遍找Win后面那个Lose就行了，还是O(N)。

过一遍找最晚时间点的结果,再过一遍找最晚时间点的相反结果

类似128，用哈希模拟桶，每次新的记录进来就找t-1的记录以及t+1的记录是否在，如果在就判断是不是胜负转换，然后尝试刷新答案。然后把当前t的记录入桶