-
Notifications
You must be signed in to change notification settings - Fork 1
/
dev.go
63 lines (52 loc) · 1.07 KB
/
dev.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
package dev
import (
"container/heap"
"math"
"github.com/catorpilor/leetcode/utils"
)
func minimumDeviation(nums []int) int {
return usePriorityQueue(nums)
}
type MaxPQ []int
func (pq MaxPQ) Len() int { return len(pq) }
func (pq MaxPQ) Less(i, j int) bool {
return pq[i] > pq[j]
}
func (pq MaxPQ) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
}
func (pq MaxPQ) Top() int {
return pq[0]
}
func (pq *MaxPQ) Push(x interface{}) {
// n := len(*pq)
item := x.(int)
*pq = append(*pq, item)
}
func (pq *MaxPQ) Pop() interface{} {
old := *pq
n := len(old)
item := old[n-1]
*pq = old[0 : n-1]
return item
}
// usePriorityQueue time complexity O(N*log(N)), space complexity O(N)
func usePriorityQueue(nums []int) int {
var pq MaxPQ
minV := math.MaxInt32
for _, num := range nums {
if num&1 != 0 {
num <<= 1
}
heap.Push(&pq, num)
minV = utils.Min(minV, num)
}
res := math.MaxInt32
for pq.Top()%2 == 0 {
res = utils.Min(res, pq.Top()-minV)
minV = utils.Min(minV, pq.Top()>>1)
heap.Push(&pq, pq.Top()>>1)
heap.Pop(&pq)
}
return utils.Min(res, pq.Top()-minV)
}