java - 在 10 分钟的窗口内存储对象

Question

我正在尝试解决面试练习中提出的问题。我在面试中无法解决它，所以我请求你的帮助。

问题是:

用一个方法编写一个类，该方法接受一个整数并返回该方法在过去十分钟内被调用的最大值的整数。

据我所知，我必须存储在过去 10 分钟内调用该方法的所有值。这些值应存储在高效的数据结构中，因为每秒可能会调用此方法数次。

对于哪种数据结构应该更有效，您有什么建议吗？另外，由于这是一个时间滚动窗口，我该如何清理过期的值？

根据所使用的数据结构，获得最大值的最佳方法应该是什么？

我有一些基本代码:

    private final static ScheduledExecutorService EXECUTOR_SERVICE = Executors.newSingleThreadScheduledExecutor(); 

    private static List<Integer> values = new ArrayList<Integer>();


    public int method(final int value){
        values.add(value);

         // Task to remove the key-value pair     
        Runnable task = new Runnable() {     
            @Override     
            public void run() {     
                values.remove(value);
            }     
        };     

        // Schedule the task to run after the delay  
        EXECUTOR_SERVICE.schedule(task, 60, TimeUnit.SECONDS);  


        //TODO get the max value
        return 1;
    }

Answer 1

定义一个 Entry类由(时间戳)time 组成和一个 (int) value ;

使用 LinkedList<Entry>保持滑动窗口:在末尾插入，在开始时删除过期。使用 TreeMap<Integer, ArrayList<Entry>>保持 O(1) 查找最大值(使用 .lastEntry() 获得最大值)。这个想法是按 value 排序并保留具有该值的所有条目的列表；对于每个添加或删除的条目，必须更新一次树(在 O(log(N)) 中。

不要使用调度器；每当新请求到达(或请求“最大”)时进行清理，它更便宜、更快。