题解 | #滑动窗口的最大值#
滑动窗口的最大值
https://www.nowcoder.com/practice/1624bc35a45c42c0bc17d17fa0cba788
package main /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @param size int整型 * @return int整型一维数组 */ func maxInWindows( nums []int , size int ) []int { // write code here if size > len(nums) || size == 0 { return nil } var result []int // 维护一个单调递减队列(索引) var deque []int for index,value := range nums { // 清理过期元素:从双端队列尾部开始,弹出所有比当前元素小的元素的索引,因为这些元素不可能是当前窗口的最大值(当前元素更大)。 for len(deque) > 0 && nums[deque[len(deque)-1]] <= value { deque = deque[:len(deque)-1] } // 将当前元素索引加入到deque中 deque = append(deque, index) // 维护双端队列:如果双端队列不为空且当前元素的索引与双端队列首部元素的索引之差等于窗口大小,则从队列首部弹出元素(这意味着窗口已经滑过这个元素)。 if deque[0] <= index - size { deque = deque[1:] } // 记录最大值:如果已经处理了窗口大小的元素(即i >= size - 1),则将双端队列首部元素对应的值添加到result数组中。 if index>= size -1 { result = append(result, nums[deque[0]]) } } return result }