題目

https://leetcode.com/problems/sliding-window-maximum/

題解

窗口內最大最小值更新結構，單調棧問題，左神視頻講過，《程序員算法面試指南》也有此題目。

本題的關鍵在于利用雙端隊列來實現窗口最大值的更新。

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {Deque<Integer> valueQueue = new LinkedList<>();Deque<Integer> indexQueue = new LinkedList<>();int[] result = new int[nums.length - k + 1];for (int i = 0; i < nums.length; i++) {if (!indexQueue.isEmpty() && indexQueue.peekFirst() <= i - k) {valueQueue.pollFirst();indexQueue.pollFirst();}while (!valueQueue.isEmpty() && valueQueue.peekLast() < nums[i]) {valueQueue.pollLast();indexQueue.pollLast();}valueQueue.offer(nums[i]);indexQueue.offer(i);if (i - k + 1 >= 0) result[i - k + 1] = valueQueue.peekFirst();}return result;} }

總結

以上是生活随笔為你收集整理的leetcode 239. Sliding Window Maximum | 239. 滑动窗口最大值（单调栈，窗口内最大最小值更新结构）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。