LeetCode 239 滑動窗口最大值

問題描述

給定一個整數(shù)數(shù)組 nums 和一個整數(shù) k，定義一個大小為 k 的滑動窗口，該窗口從數(shù)組的最左側(cè)移動到最右側(cè)。你可以看到在滑動窗口內(nèi)的 k 個數(shù)字，并返回滑動窗口中的最大值。

解題思路

我們可以利用一個雙端隊列 deque 來解決這個問題。在滑動窗口的過程中，我們需要做以下幾件事情：

1. 維護一個雙端隊列 deque，用來存儲數(shù)組元素的索引。
2. 當新的元素進入滑動窗口時，我們需要從隊列的尾部開始比較，將小于等于當前元素值的索引全部彈出，確保隊列中的元素是按照遞減順序排列的。
3. 將當前元素的索引入隊。
4. 判斷隊列中的頭部元素（即最大值的索引）是否已經(jīng)超出滑動窗口的范圍，若超出范圍則將其彈出。
5. 滑動窗口移動到達有效位置后，將隊列頭部元素對應的數(shù)組值添加到結(jié)果中。

代碼實現(xiàn)

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {deque<int> dq = {};vector<int> result = {};for (int i = 0; i < nums.size(); i++) {// 插入數(shù)值while (!dq.empty() && nums[dq.back()] <= nums[i]) {dq.pop_back();}dq.push_back(i);    // 入隊// 滑動窗口右移if (i - dq.front() >= k) {    // 隊首已經(jīng)離開窗口了dq.pop_front();}// 記錄答案if (i >= k - 1) {// 由于隊首到隊尾單調(diào)遞減，所以窗口最大值就是隊首result.push_back(nums[dq.front()]);}}return result;}
};

算法復雜度分析

• 時間復雜度：該算法只需一次遍歷數(shù)組，時間復雜度為 $O(n)$，其中 $n$ 是數(shù)組的長度。
• 空間復雜度：雙端隊列的最大空間為 $O(k)$，用于存儲滑動窗口的索引值。

總結(jié)

本文介紹了一種使用雙端隊列來解決滑動窗口最大值的問題的方法。通過維護一個單調(diào)遞減的雙端隊列，可以在 $O(n)$ 的時間復雜度內(nèi)解決該問題，其中 $n$ 是數(shù)組的長度。這種方法在面對滑動窗口問題時具有較高的效率和可讀性，是一種常見的解題思路。