刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/stock-price-fluctuation/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给你一支股票价格的数据流。数据流中每一条记录包含一个 时间戳 和该时间点股票对应的 价格 。

不巧的是，由于股票市场内在的波动性，股票价格记录可能不是按时间顺序到来的。某些情况下，有的记录可能是错的。如果两个有相同时间戳的记录出现在数据流中，前一条记录视为错误记录，后出现的记录 更正 前一条错误的记录。

请你设计一个算法，实现：

• 更新 股票在某一时间戳的股票价格，如果有之前同一时间戳的价格，这一操作将 更正 之前的错误价格。
• 找到当前记录里 最新股票价格 。最新股票价格 定义为时间戳最晚的股票价格。
• 找到当前记录里股票的 最高价格 。
• 找到当前记录里股票的 最低价格 。
  请你实现 StockPrice 类：
• StockPrice() 初始化对象，当前无股票价格记录。
• void update(int timestamp, int price) 在时间点 timestamp 更新股票价格为 price 。
• int current() 返回股票 最新价格 。
• int maximum() 返回股票 最高价格 。
• int minimum() 返回股票 最低价格 。

思路

一顿花里胡哨，但是看起来很简单的嘛~
三下五除二就写好了，然后超时了。。。不是，你也没提时间复杂度啊？！￥%
最新价格不用多说，维持一个最新时间戳即可，然后哈希表存下每个时间戳对应的最新价格即可，那问题就出在最高价格和最低价格了，O(n)时间复杂度不够，那就O(logn)，而在几种符合条件的排序算法中，最直观能想到的，就是堆排了，Go官方有一些方便堆排的函数可以借用，我们自己实现一个简单的结构就好

不过看题解发现了一个优化点，那就是不用在意删除失效数据，只要哈希表中时间戳对应的数据与堆中数据不符，那就是一条过期数据，无视即可，就不用费力去删掉了，点个赞！

代码

type StockPrice struct {
	maxTime            int
	timeMap            map[int]int
	maxPrice, minPrice IntHeap
}

func Constructor() StockPrice {
	return StockPrice{timeMap: map[int]int{}}
}

func (sp *StockPrice) Update(timestamp int, price int) {
	if sp.maxTime < timestamp {
		sp.maxTime = timestamp
	}
	sp.timeMap[timestamp] = price
	heap.Push(&sp.maxPrice, []int{-price, timestamp})
	heap.Push(&sp.minPrice, []int{price, timestamp})
}

func (sp *StockPrice) Current() int {
	return sp.timeMap[sp.maxTime]
}

func (sp *StockPrice) Maximum() int {
	for {
		cur := heap.Pop(&sp.maxPrice).([]int)
		v := sp.timeMap[cur[1]]
		if v == -cur[0] {
			heap.Push(&sp.maxPrice, cur)
			return v
		}
	}
}

func (sp *StockPrice) Minimum() int {
	for {
		cur := heap.Pop(&sp.minPrice).([]int)
		v := sp.timeMap[cur[1]]
		if v == cur[0] {
			heap.Push(&sp.minPrice, cur)
			return v
		}
	}
}

/**
 * Your StockPrice object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Update(timestamp,price);
 * param_2 := obj.Current();
 * param_3 := obj.Maximum();
 * param_4 := obj.Minimum();
 */

type IntHeap [][]int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i][0] < h[j][0] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}
func (h *IntHeap) Push(x interface{}) {
	*h = append(*h, x.([]int))
}