leetcode
leetcode 1801 ~ 1850
股票价格波动

股票价格波动

难度:

标签:

题目描述

代码结果

运行时间: 423 ms, 内存: 62.7 MB


/* 思路:使用Stream来处理集合的最大值和最小值查找。仍然使用HashMap来存储时间戳和价格的映射。 */

import java.util.HashMap;
import java.util.Map;

class StockPrice {
    private Map<Integer, Integer> timestampPriceMap;
    private int latestTimestamp;
    
    public StockPrice() {
        timestampPriceMap = new HashMap<>();
        latestTimestamp = 0;
    }
    
    public void update(int timestamp, int price) {
        if (timestamp >= latestTimestamp) {
            latestTimestamp = timestamp;
        }
        timestampPriceMap.put(timestamp, price);
    }
    
    public int current() {
        return timestampPriceMap.get(latestTimestamp);
    }
    
    public int maximum() {
        return timestampPriceMap.values().stream().mapToInt(v -> v).max().getAsInt();
    }
    
    public int minimum() {
        return timestampPriceMap.values().stream().mapToInt(v -> v).min().getAsInt();
    }
}

解释

方法:

该题解采用堆和哈希表结合的方式来维护股票价格的数据流。堆用于快速检索最大和最小价格,哈希表用于记录每个时间戳对应的价格,并跟踪最新价格。具体来说,使用两个堆,一个最大堆(存储负值以模拟最大堆)用来找到最大价格,一个最小堆用来找到最小价格。更新价格时,将价格与时间戳加入两个堆中,并更新哈希表和最新时间戳。在获取最大和最小价格时,堆顶元素如果与哈希表中的当前价格不符,则将其移除,直到堆顶元素有效。最新价格直接通过最大时间戳在哈希表中查询获得。

时间复杂度:

O(log n)(对于update, maximum, 和 minimum操作)

空间复杂度:

O(n)

代码细节讲解

🦆
堆中可能会存在无效的股票价格,你是如何保证`maximum`和`minimum`方法中返回的价格是有效的?
在`maximum`和`minimum`方法中,通过检查堆顶元素的价格与哈希表中对应时间戳的价格是否一致来确保价格的有效性。如果不一致,说明这个价格在之后被更新过,因此这个堆顶元素现在是无效的,将其从堆中移除。这个过程会重复进行,直到找到一个有效的堆顶元素。这样可以确保返回的价格总是有效的。
🦆
你是如何处理堆中可能累积的无效元素的,会不会影响性能?
通过在`maximum`和`minimum`方法中删除不再有效的堆顶元素,处理累积的无效元素。这种处理是必要的,因为每次更新操作可能会导致之前的价格失效。尽管这增加了方法的执行时间,因为每次调用可能涉及多次堆操作(如`heappop`),但通常情况下,这种影响是可接受的,特别是当价格更新不频繁或者价格变动在一定范围内时。不过,极端情况下,如果有大量冗余数据,性能可能会受到影响。
🦆
在确定最新股票价格时,你是如何确保`current`方法中返回的价格总是最新的?
在每次调用`update`方法时,都会更新哈希表`timePriceMap`来记录每个时间戳对应的价格,并更新一个变量`maxTimestamp`保持迄今为止的最大时间戳。在`current`方法中,直接通过`maxTimestamp`从哈希表中获取最新时间戳对应的价格。这样可以保证,无论何时调用`current`方法,都能够返回最新的股票价格。
🦆
为什么选择使用两个堆(一个最大堆和一个最小堆)来维护股票的价格,而不是使用其他数据结构?
使用两个堆(一个最大堆和一个最小堆)可以有效地提供对最大和最小股票价格的快速访问,这是因为堆结构能够让我们快速地找到最大值和最小值(堆顶元素)。其他数据结构如平衡二叉搜索树虽然也能提供这些功能,并支持更快的删除和搜索操作,但在简化实现和减少维护复杂性方面,使用堆更为直接和有效。此外,堆的插入和删除操作时间复杂度为O(log n),适用于频繁更新和查询极值的场景。

相关问题