电子政务与网站建设方面,企业vi系统设计公司,自己有产品怎么网络销售,广告设计公司产品239. 滑动窗口最大值
困难 给你一个整数数组 nums#xff0c;有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。
示例 1#xff1a; 输入#xff1a;nums [1,…239. 滑动窗口最大值
困难 给你一个整数数组 nums有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。
示例 1 输入nums [1,3,-1,-3,5,3,6,7], k 3 输出[3,3,5,5,6,7] 解释 滑动窗口的位置 最大值 [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 示例 2 输入nums [1], k 1 输出[1]
提示
1 nums.length 10(5)-10(4) nums[i] 10(4)1 k nums.length 思路 设计单调队列的时候pop和push操作要保持如下规则
pop(value)如果窗口移除的元素value等于单调队列的出口元素那么队列弹出元素否则不用任何操作push(value)如果push的元素value大于入口元素的数值那么就将队列入口的元素弹出直到push元素的数值小于等于队列入口元素的数值为止 保持如上规则每次窗口移动的时候只要问que.front()就可以返回当前窗口的最大值。 优先级队列正式登场大顶堆、小顶堆该怎么用| LeetCode347.前 K 个高频元素
维护了一个单调栈
代码
func maxSlidingWindow(nums []int, k int) []int {if len(nums) 0 {return []int{}}var result []intvar queue []intfor i : 0; i len(nums); i {// 移除队列中不在当前窗口的元素for len(queue) 0 queue[0] i-k1 {queue queue[1:]}// 移除队列尾部小于当前元素的元素保持递减顺序for len(queue) 0 nums[queue[len(queue)-1]] nums[i] {queue queue[:len(queue)-1]}// 将当前元素的下标加入队列queue append(queue, i)// 将队列头部元素作为当前窗口的最大值if i k-1 {result append(result, nums[queue[0]])}}return result
}347. 前 K 个高频元素
中等 给你一个整数数组 nums 和一个整数 k 请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1: 输入: nums [1,1,1,2,2,3], k 2 输出: [1,2] 示例 2: 输入: nums [1], k 1 输出: [1]
提示
1 nums.length 10(5)k 的取值范围是 [1, 数组中不相同的元素的个数]题目数据保证答案唯一换句话说数组中前 k 个高频元素的集合是唯一的
进阶你所设计算法的时间复杂度 必须 优于 O(n log n) 其中 n 是数组大小。
思路
用小顶堆因为要统计最大前k个元素只有小顶堆每次将最小的元素弹出最后小顶堆里积累的才是前k个最大元素。 代码我们首先创建了一个自定义的类型 MinHeap并让它实现了 heap.Interface 接口中的 Len、Less、Swap、Push 和 Pop 方法。在 MinHeap 类型中我们重新定义了 Less 和 Swap 方法以满足小顶堆的性质。当我们创建一个 MinHeap 类型的变量 minHeap 后可以使用 heap.Push 方法将元素添加到堆中而 heap.Pop 方法则会从堆中弹出最小的元素以保持小顶堆的性质。
代码
package stack_queueimport (container/heap
)// topKFrequent 返回整数数组 nums 中出现频率前 k 高的元素
func topKFrequent(nums []int, k int) []int {// 创建一个映射用于记录每个元素出现的次数mapNum : map[int]int{}// 记录每个元素出现的次数for _, item : range nums {mapNum[item]}// 创建一个小顶堆h : IHeap{}heap.Init(h)// 将所有元素入堆堆的长度限制为 kfor key, value : range mapNum {heap.Push(h, [2]int{key, value})if h.Len() k {heap.Pop(h)}}// 创建一个结果切片res : make([]int, k)// 按顺序从堆中弹出元素将其放入结果切片中for i : 0; i k; i {res[k-i-1] heap.Pop(h).([2]int)[0]}return res
}// IHeap 定义一个小顶堆类型
type IHeap [][2]int// Len 返回堆的元素数量
func (h IHeap) Len() int {return len(h)
}// Less 比较两个元素在堆中的大小
func (h IHeap) Less(i, j int) bool {// 根据出现次数比较return h[i][1] h[j][1]
}// Swap 交换堆中的两个元素
func (h IHeap) Swap(i, j int) {h[i], h[j] h[j], h[i]
}// Push 向堆中添加元素
func (h *IHeap) Push(x interface{}) {*h append(*h, x.([2]int))
}// Pop 从堆中弹出元素
func (h *IHeap) Pop() interface{} {old : *hn : len(old)x : old[n-1]*h old[0 : n-1]return x
}
