Week 18 @ 2025 算法周记【单调栈 + 单调队列】
单调栈
LC 581. Shortest Unsorted Continuous Subarray 最短无序连续子数组
https://leetcode.com/problems/shortest-unsorted-continuous-subarray/description/
排序比较
func findUnsortedSubarray(nums []int) int {
sorted := append([]int{}, nums...)
sort.Ints(sorted)
l := 0
r := len(nums) - 1
any := false
for i := 0; i < len(nums); i++ {
if nums[i] != sorted[i] {
l = i
any = true
break
}
}
for i := len(nums) - 1; i >= 0 ; i-- {
if nums[i] != sorted[i] {
r = i
any = true
break
}
}
if !any {
return 0
}
return r - l + 1
}func findUnsortedSubarray(nums []int) int {
sorted := append([]int{}, nums...)
sort.Ints(sorted)
l := -1
r := -1
for i := 0; i < len(nums); i++ {
if nums[i] != sorted[i] {
l = i
break
}
}
for i := len(nums) - 1; i >= 0 ; i-- {
if nums[i] != sorted[i] {
r = i
break
}
}
if l == -1 { // l r 只能同时为 -1 或同时不为 -1；-1 代表本就有序
return 0
}
return r - l + 1
}单调栈
func findUnsortedSubarray(nums []int) int {
l := len(nums)
stack := make([]int, 0, len(nums))
for i := 0; i < len(nums); i++ {
for len(stack) > 0 && nums[stack[len(stack)-1]] > nums[i] {
l = min(l, stack[len(stack)-1])
stack = stack[:len(stack)-1]
}
stack = append(stack, i)
}
r := -1
stack = make([]int, 0, len(nums))
for i := len(nums) - 1; i >= 0 ; i-- {
for len(stack) > 0 && nums[stack[len(stack)-1]] < nums[i] {
r = max(r, stack[len(stack)-1])
stack = stack[:len(stack)-1]
}
stack = append(stack, i)
}
if r == -1 { // l r 只能同时为 -1 或同时不为 -1；-1 代表本就有序
return 0
}
return r - l + 1
}单调队列
实现可计算最大最小值的单调队列
type MonotonicQueue struct {
q []int
maxq []int
minq []int
}
func NewMonotonicQueue() *MonotonicQueue {
return &MonotonicQueue{
q: []int{},
maxq: []int{},
minq: []int{},
}
}
func (q *MonotonicQueue) Push(elem int) {
q.q = append(q.q, elem)
// maxq: 5 3 3 1
for len(q.maxq) > 0 && q.maxq[len(q.maxq)-1] < elem {
q.maxq = q.maxq[:len(q.maxq)-1]
}
q.maxq = append(q.maxq, elem)
// minq: 1 3 3 5
for len(q.minq) > 0 && q.minq[len(q.minq)-1] > elem {
q.minq = q.minq[:len(q.minq)-1]
}
q.minq = append(q.minq, elem)
}
func (q *MonotonicQueue) Pop() int {
elem := q.q[0]
q.q = q.q[1:]
if q.maxq[0] == elem {
q.maxq = q.maxq[1:]
}
if q.minq[0] == elem {
q.minq = q.minq[1:]
}
return elem
}
func (q *MonotonicQueue) Max() int {
return q.maxq[0]
}
func (q *MonotonicQueue) Min() int {
return q.minq[0]
}
func (q *MonotonicQueue) Size() int {
return len(q.q)
}
func (q *MonotonicQueue) IsEmpty() bool {
return len(q.q) == 0
}LC 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit 绝对差不超过限制的最长连续子数组
func longestSubarray(nums []int, limit int) int {
result := 0
l, r := 0, 0
q := NewMonotonicQueue()
for r < len(nums) {
q.Push(nums[r])
for l < r && q.Max() - q.Min() > limit {
q.Pop()
l++
}
result = max(result, r - l + 1)
r++
}
return result
}
type MonotonicQueue struct {
q []int
maxq []int
minq []int
}
func NewMonotonicQueue() *MonotonicQueue {
return &MonotonicQueue{
q: []int{},
maxq: []int{},
minq: []int{},
}
}
func (q *MonotonicQueue) Push(elem int) {
q.q = append(q.q, elem)
// maxq: 5 3 3 1
for len(q.maxq) > 0 && q.maxq[len(q.maxq)-1] < elem {
q.maxq = q.maxq[:len(q.maxq)-1]
}
q.maxq = append(q.maxq, elem)
// minq: 1 3 3 5
for len(q.minq) > 0 && q.minq[len(q.minq)-1] > elem {
q.minq = q.minq[:len(q.minq)-1]
}
q.minq = append(q.minq, elem)
}
func (q *MonotonicQueue) Pop() int {
elem := q.q[0]
q.q = q.q[1:]
if q.maxq[0] == elem {
q.maxq = q.maxq[1:]
}
if q.minq[0] == elem {
q.minq = q.minq[1:]
}
return elem
}
func (q *MonotonicQueue) Max() int {
return q.maxq[0]
}
func (q *MonotonicQueue) Min() int {
return q.minq[0]
}
func (q *MonotonicQueue) Size() int {
return len(q.q)
}
func (q *MonotonicQueue) IsEmpty() bool {
return len(q.q) == 0
}两个 Heap 的解法
func longestSubarray(nums []int, limit int) int {
result := 0
h := &MinMaxHeap{}
l, r := 0, 0
for r < len(nums) {
h.Push(nums[r], r)
for l < r && h.Max() - h.Min() > limit {
l = h.Pop()
}
result = max(result, r - l + 1)
r++
}
return result
}
type MinMaxHeap struct {
minh MinHeap
maxh MinHeap
}
func (h *MinMaxHeap) Max() int {
return -h.maxh[0][0]
}
func (h *MinMaxHeap) Min() int {
return h.minh[0][0]
}
func (h *MinMaxHeap) Push(v int, index int) {
heap.Push(&h.minh, []int{v, index})
heap.Push(&h.maxh, []int{-v, index})
}
func (h *MinMaxHeap) Pop() int {
newLeft := min(h.minh[0][1], h.maxh[0][1]) + 1
for h.minh[0][1] < newLeft {
heap.Pop(&h.minh)
}
for h.maxh[0][1] < newLeft {
heap.Pop(&h.maxh)
}
return newLeft
}
type MinHeap [][]int
func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i][0] < h[j][0] }
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x any) {
// Push and Pop use pointer receivers because they modify the slice's length,
// not just its contents.
*h = append(*h, x.([]int))
}
func (h *MinHeap) Pop() any {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
LC 862. Shortest Subarray with Sum at Least K 和至少为 K 的最短子数组
https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/description/
单调栈解法
func shortestSubarray(nums []int, k int) int {
preSum := getPreSum(nums)
q := NewMonotonicQueue()
result := math.MaxInt
l, r := 0, 0
for r < len(preSum) {
q.Push(preSum[r])
r++
for r < len(preSum) && !q.IsEmpty() && preSum[r] - q.Min() >= k {
result = min(result, r-l)
q.Pop()
l++
}
}
if result == math.MaxInt {
return -1
}
return result
}
func getPreSum(nums []int) []int {
preSum := make([]int, len(nums) + 1)
for i := 0; i < len(nums); i++ {
preSum[i+1] = preSum[i] + nums[i]
}
return preSum
}
type MonotonicQueue struct {
q []int
maxq []int
minq []int
}
func NewMonotonicQueue() *MonotonicQueue {
return &MonotonicQueue{
q: []int{},
maxq: []int{},
minq: []int{},
}
}
func (q *MonotonicQueue) Push(elem int) {
q.q = append(q.q, elem)
// maxq: 5 3 3 1
for len(q.maxq) > 0 && q.maxq[len(q.maxq)-1] < elem {
q.maxq = q.maxq[:len(q.maxq)-1]
}
q.maxq = append(q.maxq, elem)
// minq: 1 3 3 5
for len(q.minq) > 0 && q.minq[len(q.minq)-1] > elem {
q.minq = q.minq[:len(q.minq)-1]
}
q.minq = append(q.minq, elem)
}
func (q *MonotonicQueue) Pop() int {
elem := q.q[0]
q.q = q.q[1:]
if q.maxq[0] == elem {
q.maxq = q.maxq[1:]
}
if q.minq[0] == elem {
q.minq = q.minq[1:]
}
return elem
}
func (q *MonotonicQueue) Max() int {
return q.maxq[0]
}
func (q *MonotonicQueue) Min() int {
return q.minq[0]
}
func (q *MonotonicQueue) Size() int {
return len(q.q)
}
func (q *MonotonicQueue) IsEmpty() bool {
return len(q.q) == 0
}堆解法
func shortestSubarray(nums []int, k int) int {
result := math.MaxInt
sum := 0
h := Heap{}
for i, num := range nums {
sum += num
if sum >= k {
result = min(result, i+1)
}
for h.Len() > 0 && sum - h[0][0] >= k {
result = min(result, i - h[0][1])
heap.Pop(&h)
}
heap.Push(&h, []int{sum, i})
}
if result == math.MaxInt {
return -1
}
return result
}
type Heap [][]int
func (h Heap) Len() int { return len(h) }
func (h Heap) Less(i, j int) bool { return h[i][0] < h[j][0] }
func (h Heap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *Heap) Push(x any) {
// Push and Pop use pointer receivers because they modify the slice's length,
// not just its contents.
*h = append(*h, x.([]int))
}
func (h *Heap) Pop() any {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}