239.滑动窗口最大值
239.滑动窗口最大值
题解
题目：给一个数组，再给一个k大小的滑动窗口，求窗口内的最大值
思路：优先队列 和 单调栈
1.维护一个单调递减队列 2.对于窗口右移，就是往队列中插入，与删除 3.而删除需要遍历，但是本题其实不急着删除，即延迟删除 4.也就是说当nums[i-k] == queue[0]的时候，就可以删除，这样就是O(1) 5.对于插入，需要维护递减，如果插入v大于下面的，则弹出下面的即可 例如：[5,6,1,2]3 -->[6,1] ans0=6 -->[6,2] ans1=6 例如：[6,5,1,2]3 -->[6,5,1]ans0=6 --> nums[i-k] == queue[0]--->[5,2]ans1=2
代码
type PriorityQueue struct { queue []int } func (pq *PriorityQueue) Push(v int) { for !pq.IsEmpty() && v > pq.Back() { pq.queue = pq.queue[:len(pq.queue)-1] } pq.queue = append(pq.queue, v) } func (pq *PriorityQueue) Pop(v int) { if pq.Front() == v { pq.queue = pq.queue[1:] } } func (pq *PriorityQueue) Front() int { return pq.queue[0] } func (pq *PriorityQueue) Back() int { return pq.queue[len(pq.queue)-1] } func (pq *PriorityQueue) IsEmpty() bool { return len(pq.queue) == 0 } func maxSlidingWindow(nums []int, k int) []int { pq := PriorityQueue{queue: make([]int, 0)} ans := make([]int, 0) for i := 0; i < k; i++ { pq.Push(nums[i]) } ans = append(ans, pq.Front()) for i := k; i < len(nums); i++ { pq.Pop(nums[i-k]) pq.Push(nums[i]) ans = append(ans, pq.Front()) } return ans }
func maxSlidingWindow(nums []int, k int) []int { stack := make([]int, 0) var push func(v int) push = func(v int) { for len(stack) >= 0 && v > stack[len(stack)-1] { stack = stack[:len(stack)-1] } stack = append(stack, v) } ans := make([]int, 0) for i := 0; i < k; i++ { push(nums[i]) } ans = append(ans, stack[0]) for i := k; i < len(nums); i++ { push(nums[i]) if nums[i-k] == stack[0] { stack = stack[1:] } ans = append(ans, stack[0]) } return ans }
