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  // @Title: 滑动窗口最大值 (Sliding Window Maximum) // @Author: 15816537946@163.com // @Date: 2021-01-02 23:35:25 // @Runtime: 316 ms // @Memory: 9.8 MB // 优先队列（小根堆） var a []int type hp struct{ sort.IntSlice } func (h *hp) Less(i, j int) bool { return a[h.IntSlice[i]] > a[h.IntSlice[j]] } func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) } func (h *hp) Pop() interface{} { a := h.IntSlice v := a[len(a)-1] h.IntSlice = a[:len(a)-1] return v } func maxSlidingWindow(nums []int, k int) []int { a = nums q := &hp{make([]int, k)} for i := 0; i < k; i++ { q.IntSlice[i] = i } heap.Init(q) // nums 从小到大排列，大根堆 n := len(nums) ans := make([]int, 1, n-k+1) ans[0] = nums[q.IntSlice[0]] for i := k; i < n; i++ { heap.Push(q, i) for q.IntSlice[0] <= i-k { heap.Pop(q) } ans = append(ans, nums[q.IntSlice[0]]) } return ans } /* n := len(nums) ans := make([]int, 1, n-k+1) ans[0] = nums[q.IntSlice[0]] for i := k; i < n; i++ { heap.Push(q, i) for q.IntSlice[0] <= i-k { heap.Pop(q) } ans = append(ans, nums[q.IntSlice[0]]) } return ans } */