两种做法，第一种，heap包，具体使用看代码，维护一个大根堆和一个小根堆。第二种，用slice模拟Priority queue
代码package main
import "container/heap"
type pair struct {
timestamp, price int
}
type hp []pair
func (h hp) Len() int {
return len(h)
}
func (h hp) Less(i, j int) bool {
return h[i].price < h[j].price
}
func (h hp) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *hp) Push(x interface{}) {
*h = append(*h, x.(pair))
}
func (h *hp) Pop() interface{} {
cntHeap := *h
val := cntHeap[h.Len()-1]
*h = cntHeap[:h.Len()-1]
return val
}
type StockPrice struct {
mp map[int]int
cur int
maxHp, minHp hp
}
func Constructor() StockPrice {
return StockPrice{
mp: map[int]int{},
cur: 0,
}
}
func (this *StockPrice) Update(timestamp int, price int) {
if timestamp > this.cur {
this.cur = timestamp
}
this.mp[timestamp] = price
heap.Push(&this.maxHp, pair{
timestamp: timestamp,
price: -price,
})
heap.Push(&this.minHp, pair{
timestamp: timestamp,
price: price,
})
}
func (this *StockPrice) Current() int {
return this.mp[this.cur]
}
func (this *StockPrice) Maximum() int {
for {
pri := this.maxHp[0]
if pri.price == -this.mp[pri.timestamp] {
return -pri.price
} else {
heap.Pop(&this.maxHp)
}
}
}
func (this *StockPrice) Minimum() int {
for {
pri := this.minHp[0]
if pri.price == this.mp[pri.timestamp] {
return pri.price
} else {
heap.Pop(&this.minHp)
}
}
}
package main
type StockPrice struct {
currPrice int
timeStamp int
timeToPriMap map[int]int
priQue []int
}
func Constructor() StockPrice {
return StockPrice{
currPrice: 0,
timeStamp: 0,
timeToPriMap: make(map[int]int),
priQue: make([]int, 0),
}
}
func (this *StockPrice) Update(timestamp int, price int) {
if timestamp >= this.timeStamp {
this.timeStamp = timestamp
this.currPrice = price
}
if oldPri, ok := this.timeToPriMap[timestamp]; ok {
l, r := 0, len(this.priQue)-1
for l+1 < r {
mid := l + (r-l)/2
if this.priQue[mid] <= oldPri {
l = mid
} else {
r = mid
}
}
idx := r
if this.priQue[l] == oldPri {
idx = l
}
//把旧的数据找到并删除
copy(this.priQue[idx:], this.priQue[idx+1:])
this.priQue = this.priQue[:len(this.priQue)-1]
}
this.timeToPriMap[timestamp] = price
l, r := 0, len(this.priQue)-1
for l+1 < r {
mid := l + (r-l)/2
if this.priQue[mid] <= price {
l = mid
} else {
r = mid
}
}
idx := 0
if len(this.priQue) != 0 {
if this.priQue[l] >= price {
idx = l
} else if this.priQue[r] >= price {
idx = r
} else if this.priQue[r] < price {
idx = r + 1
}
}
//把新的数据插入
this.priQue = append(this.priQue, 0)
copy(this.priQue[idx+1:], this.priQue[idx:])
this.priQue[idx] = price
}
func (this *StockPrice) Current() int {
return this.currPrice
}
func (this *StockPrice) Maximum() int {
return this.priQue[len(this.priQue)-1]
}
func (this *StockPrice) Minimum() int {
return this.priQue[0]
}