LeetCode讲解篇之239. 滑动窗口最大值

题目描述

题解思路

我们维护一个长度为k的窗口，然后窗口从数组最左边一直移动到最右边，记录过程中窗口中的最大值，就是答案
我们每次查询长度为k的窗口最大值是什么时间复杂度是O(k)的，我们可以使用单调栈进行优化，能够让查找窗口最大值的操作时间复杂度为O(1)
我们维护一个单调栈，单调栈中每个元素是数组元素的下标和数组元素的值
每次窗口向右移动，我们将当前元素加入单调栈，如果当前元素大于栈顶元素则弹出栈顶元素，循环这个过程直至栈空，或者栈顶元素大于当前元素，然后将当前元素压入栈中，然后检查如果栈底元素的数组下标在小于窗口左边界下标，则舍弃栈底元素，然后此时栈底元素的数组元素就是当前窗口中的最大值

题解代码

func maxSlidingWindow(nums []int, k int) []int {
    st := [][2]int{[2]int{0, nums[0]}}

    ans := make([]int, 0, len(nums) - k + 1)

    for i := 1; i < k; i++ {
        for len(st) > 0 && st[len(st) - 1][1] < nums[i] {
            st = st[:len(st) - 1]
        }
        st = append(st, [2]int{i, nums[i]})
    }

    ans = append(ans, st[0][1])

    for i := k; i < len(nums); i++ {
        for len(st) > 0 && st[len(st) - 1][1] < nums[i] {
            st = st[:len(st) - 1]
        }
        st = append(st, [2]int{i, nums[i]})

        if i - st[0][0] == k {
            st = st[1:]
        }

        ans = append(ans, st[0][1])
    }

    return ans
}

题目链接

https://leetcode.cn/problems/sliding-window-maximum/description/