Week 17 @ 2025 算法周记【单调队列 + 单调栈】
单调队列
LC 239. Sliding Window Maximum 滑动窗口最大值
https://leetcode.com/problems/sliding-window-maximum/description/
func maxSlidingWindow(nums []int, k int) []int {
q := NewMonotonicQueue()
result := make([]int, 0, len(nums))
for i := 0; i < k; i++ {
q.Push(nums[i])
}
result = append(result, q.Max())
for i := k; i < len(nums); i++ {
q.Push(nums[i])
q.Pop(nums[i-k])
result = append(result, q.Max())
}
return result
}
type MonotonicQueue struct {
l *list.List
}
func NewMonotonicQueue() *MonotonicQueue {
return &MonotonicQueue {
l: list.New(),
}
}
func (q *MonotonicQueue) Push(x int) {
for {
back := q.l.Back()
if back == nil || back.Value.(int) >= x {
break
}
q.l.Remove(back)
}
q.l.PushBack(x)
}
func (q *MonotonicQueue) Pop(x int) {
front := q.l.Front()
if front.Value == x {
q.l.Remove(front)
}
}
func (q *MonotonicQueue) Max() int {
return q.l.Front().Value.(int)
}单调栈
LC 1019. Next Greater Node In Linked List 链表中的下一个更大节点
https://leetcode.com/problems/next-greater-node-in-linked-list/description/
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func nextLargerNodes(head *ListNode) []int {
values := toValues(head)
n := len(values)
result := make([]int, n)
stack := make([]int, 0, n)
for i := n-1; i >= 0; i-- {
for len(stack) > 0 && stack[len(stack)-1] <= values[i] {
stack = stack[:len(stack)-1]
}
if len(stack) > 0 {
result[i] = stack[len(stack)-1]
}
stack = append(stack, values[i])
}
return result
}
func toValues(head *ListNode) []int {
values := make([]int, 0, 1_0000)
for head != nil {
values = append(values, head.Val)
head = head.Next
}
return values
}LC 1944. Number of Visible People in a Queue 队列中可以看到的人数
https://leetcode.com/problems/number-of-visible-people-in-a-queue/description/
func canSeePersonsCount(heights []int) []int {
result := make([]int, len(heights))
stack := make([]int, 0, len(heights))
for i := len(heights) - 1; i >= 0; i-- {
count := 0
for len(stack) > 0 && stack[len(stack)-1] < heights[i] {
stack = stack[:len(stack)-1]
// 统计到「下一个等高或更高元素之间」有几个元素（已剔除被遮挡元素）
count++
}
if len(stack) > 0 {
result[i] = count + 1 // 也能看到「下一个等高或更高元素」
} else {
result[i] = count
}
stack = append(stack, heights[i])
}
return result
}LC 1475. Final Prices With a Special Discount in a Shop 商品折扣后的最终价格
https://leetcode.com/problems/final-prices-with-a-special-discount-in-a-shop/description/
func finalPrices(prices []int) []int {
n := len(prices)
result := make([]int, n)
stack := make([]int, 0, n)
for i := n-1; i >= 0; i-- {
// 找到下一个更小或相等元素
for len(stack) > 0 && stack[len(stack)-1] > prices[i] {
stack = stack[:len(stack)-1]
}
if len(stack) > 0 {
result[i] = prices[i] - stack[len(stack)-1]
} else {
result[i] = prices[i]
}
stack = append(stack, prices[i])
}
return result
}LC 901. Online Stock Span 股票价格跨度
https://leetcode.com/problems/online-stock-span/description/
type StockSpanner struct {
stack []Value
day int
}
type Value struct {
price int
index int
}
func Constructor() StockSpanner {
return StockSpanner{
day: -1,
}
}
func (this *StockSpanner) Next(price int) int {
// 向前找 > 当前值的 index === 栈内剔除 <= 当前值的元素
for len(this.stack) > 0 && this.stack[len(this.stack)-1].price <= price {
this.stack = this.stack[:len(this.stack)-1]
}
this.day++
var result int
if len(this.stack) > 0 {
lastDayIndex := this.stack[len(this.stack)-1].index
result = this.day - lastDayIndex
} else {
result = this.day + 1
}
this.stack = append(this.stack, Value{price, this.day})
return result
}
/**
* Your StockSpanner object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Next(price);
*/LC 402. Remove K Digits 移掉 K 位数字
https://leetcode.com/problems/remove-k-digits/description/
func removeKdigits(num string, k int) string {
digits := []byte(num)
n := len(digits)
stack := make([]byte, 0, n)
for _, digit := range digits {
for k > 0 && len(stack) > 0 && stack[len(stack)-1] > digit {
k--
stack = stack[:len(stack)-1]
}
stack = append(stack, digit)
}
for k > 0 && len(stack) > 0 {
k--
stack = stack[:len(stack)-1]
}
return toString(stack)
}
func toString(digits []byte) string {
for len(digits) > 0 && digits[0] == '0' {
digits = digits[1:]
}
if len(digits) == 0 {
return "0"
}
return string(digits)
}LC 853. Car Fleet 车队
https://leetcode.com/problems/car-fleet/description/
func carFleet(target int, position []int, speed []int) int {
cars := make([][]int, len(position))
for i := range cars {
cars[i] = []int{position[i], speed[i]}
}
slices.SortFunc(cars, func(a, b []int) int {
return a[0] - b[0]
})
times := make([]float64, len(cars))
for i, car := range cars {
times[i] = float64(target-car[0]) / float64(car[1])
}
count := 0
maxTimes := 0.0
for i := len(times) - 1; i >= 0; i-- {
if times[i] > maxTimes {
count++
maxTimes = times[i]
}
}
return count
}