leetcode | go | 第632题 | 最小区间

最小区间

go

解决思路

1. 堆 hp 为 [3]int 构建起来的数组，第 0 个元素代表值，第 1 个元素代表在 nums 中的索引 i，第二个元素代表在 nums[i] 中的索引 j
2. 构建最小堆 h，max 设为?math.MinInt32（代表当前堆中最大元素），minLen 设为?math.MaxInt32（区间的最小长度），ans 为 int 数组
3. 因为每个整数列表都至少要有一个数，所以我们先把 nums 中每个列表的第 0 个元素放入堆中，并在此过程中更新 max
4. 当 minLen>0 一直循环（第一个 =0 的情况，此后不会再减小区间长度，且当前区间左端点最小，所以可以结束循环），取出堆顶元素（转化为 [3]int）赋给 x（即为区间的左端点），如果 max - x[0] < minLen，更新 minLen 和 ans（多个相同最小值怎么办呢，取出一个更新，区间的左端点不会变化，只可能增加右端点，直到所有相同最小值被取出，才有可能减小 minLen，所以先取或后取，取出的顺序不重要）。如果当前元素已经在列表的最末端，那么区间左端点无法更大，再往后只会增大区间右端点，break。否则取出列表的下一位元素，更新 max，加入堆中
5. return ans
6. 题解思路：（1）贪心 + 最小堆（2）哈希表 + 滑动窗口?

相关问题

1. 终于 ┭┮﹏┭┮，最后一道困难题了
2. 标签：贪心、数组、哈希表、排序、滑动窗口、堆（优先队列）
3. pop 出来的是一个 interface 还要转化为 [3]int，而且 [3]int 还要加括号
4. 是我想的太复杂了
5. 忘记更新 max 了
6. 怎么还差 4 个就 AC 了，鼠鼠又要玉玉了，还让不让鼠鼠吃饭啦
7. 原来是我把 minLen 弄错了，最小的情况可以为 0，等于 0 就可以停止循环了

func smallestRange(nums [][]int) []int {
    h:=&hp{}
    max:=math.MinInt32
    minLen:=math.MaxInt32
    ans:=[]int{}
    for i,num:=range nums {
        heap.Push(h,[3]int{num[0],i,0})
        if num[0]>max {
            max=num[0]
        }
    }
    for minLen>0 {
        x:=heap.Pop(h).([3]int)
        if minLen>max-x[0] {
            ans=[]int{x[0],max}
            minLen=max-x[0]
        }
        if len(nums[x[1]])==x[2]+1 {
            break
        }
        y:=nums[x[1]][x[2]+1]
        if y>max {
            max=y
        }
        heap.Push(h,[3]int{y,x[1],x[2]+1})
    }

    return ans
}

type hp [][3]int
func (h hp) Len() int            { return len(h) }
func (h hp) Less(i, j int) bool  { return h[i][0]<h[j][0]}
func (h hp) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v interface{}) { *h = append(*h, v.([3]int)) }
func (h *hp) Pop() interface{}   { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }