2034. 股票价格波动

过错是暂时的遗憾，而错过则是永远的遗憾!不要害怕过错而错过。

前言

国庆节结束，准备重新开始出发，继续更新博客。最近在学习kotlin这门语言，顺便在LeetCode这个网站练习使用。kotlin语言还是比较新的，站在前人的肩膀上，吸收了很多其他语言的高级特性，和Java完全兼容。

题目

LC每日一题，参考2034. 股票价格波动，难度分1832。

解题思路

• 哈希表+优先队列：设计题，考虑使用哈希表来存储键值对数据。对于最新数据可以在更新时记录最大时间戳即可；对于最值，考虑使用优先队列，因为堆里面只维护大根或小根所以需要使用两个优先队列，在更新时直接插入新的键值对（使用数组存储或Map.Entry），在取最大最小值时，可以取出根值和哈希表里面正确的值作比较，如果不相同说明是过期的数据直接出队列，继续取出下一个进行比较，若相等则直接返回。

哈希表+优先队列 解法

class StockPrice() {

    //考虑使用哈希表map和优先队列PriorityQueue实现
    val arr = mutableMapOf<Int,Int>()
    val pq1 = PriorityQueue<Array<Int>>{a,b->b[1]-a[1]} // 大根堆
    val pq2 = PriorityQueue<Array<Int>>{a,b->a[1]-b[1]} // 小根堆
    var maxTime = 0
    fun update(timestamp: Int, price: Int) {
        if(timestamp > maxTime) maxTime = timestamp
        arr[timestamp] = price
        pq1.offer(arrayOf(timestamp,price))
        pq2.offer(arrayOf(timestamp,price))
    }

    fun current(): Int  = arr[maxTime]!!

    fun maximum(): Int {
        while(true) { // pq1.size > 0
            val top = pq1.peek()!! // 拿到队首价格判断价格是否过期
            if(arr[top[0]] == top[1]) return top[1]
            pq1.poll()
        }
    }

    fun minimum(): Int {
        while(true) {
            val top = pq2.peek()!! // 拿到队首价格判断价格是否过期
            if(arr[top[0]] == top[1]) return top[1]
            pq2.poll()
        }
    }

}

/**
 * Your StockPrice object will be instantiated and called as such:
 * var obj = StockPrice()
 * obj.update(timestamp,price)
 * var param_2 = obj.current()
 * var param_3 = obj.maximum()
 * var param_4 = obj.minimum()
 */

复杂度分析

• 时间复杂度：更新操作和最新数据都为O(1)，取最值为O(logn)，n为队列长度也即更新次数。
• 空间复杂度：O(n)。

2023.10.8