力扣日記：【棧與隊(duì)列篇】滑動(dòng)窗口最大值

日期：2023.10.30
參考：代碼隨想錄、力扣

239. 滑動(dòng)窗口最大值

題目描述

難度：困難

給你一個(gè)整數(shù)數(shù)組 nums，有一個(gè)大小為 k 的滑動(dòng)窗口從數(shù)組的最左側(cè)移動(dòng)到數(shù)組的最右側(cè)。你只可以看到在滑動(dòng)窗口內(nèi)的 k 個(gè)數(shù)字?；瑒?dòng)窗口每次只向右移動(dòng)一位。

返回 滑動(dòng)窗口中的最大值 。

示例 1：

輸入：nums = [1,3,-1,-3,5,3,6,7], k = 3
輸出：[3,3,5,5,6,7]
解釋：
滑動(dòng)窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       31 [3  -1  -3] 5  3  6  7       31  3 [-1  -3  5] 3  6  7       51  3  -1 [-3  5  3] 6  7       51  3  -1  -3 [5  3  6] 7       61  3  -1  -3  5 [3  6  7]      7

示例 2：

輸入：nums = [1], k = 1
輸出：[1]

提示：

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 1 <= k <= nums.length

題解

class Solution {
#define SOLUTION 2
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {
#if SOLUTION == 1 // 暴力解法，超出時(shí)間限制// O(n * k), O(1)vector<int> result; for (int i = 0; i <= nums.size() - k; i++) {int q_max = nums[i];for (int j = i + 1; j < i + k; j++) {if (nums[j] > q_max) {q_max = nums[j];}}result.push_back(q_max);}return result;}
#elif SOLUTION == 2 // 單調(diào)隊(duì)列// O(n), O(k)// 單調(diào)隊(duì)列的特點(diǎn)：隊(duì)列頭部為隊(duì)列中元素的最大值（或最小值），且成單調(diào)遞減（或遞增）// 當(dāng)push元素進(jìn)隊(duì)列時(shí)，隊(duì)列中比所push元素小的需全部彈出（從尾部彈出）// 當(dāng)pop元素出隊(duì)列時(shí)，只有隊(duì)列頭部為需pop元素時(shí)才需pop（否則該元素已經(jīng)在push時(shí)就被彈出了）/* //這種寫(xiě)法當(dāng)k=n時(shí)會(huì)有問(wèn)題....MyQueue mQ;vector<int> result;for (int i = 0; i < nums.size(); i++) {while (i < k) { // 注意++不能放在while()條件中，否則每次判斷一次都會(huì)+1mQ.push(nums[i]);i++;}result.push_back(mQ.getMaxValue());// 先push先pop都可以mQ.push(nums[i]);mQ.pop(nums[i - k]); // pop也需要輸入值}result.push_back(mQ.getMaxValue()); // 記得最后一個(gè)窗口return result;*/MyQueue que;vector<int> result;for (int i = 0; i < k; i++) { // 先將前k的元素放進(jìn)隊(duì)列que.push(nums[i]);}result.push_back(que.getMaxValue()); // result 記錄前k的元素的最大值for (int i = k; i < nums.size(); i++) {que.pop(nums[i - k]); // 滑動(dòng)窗口移除最前面元素que.push(nums[i]); // 滑動(dòng)窗口前加入最后面的元素result.push_back(que.getMaxValue()); // 記錄對(duì)應(yīng)的最大值}return result;}
private:class MyQueue { // 單調(diào)隊(duì)列（從大到小）public:deque<int> que; // 使用deque，兩邊都可pop// 每次彈出的時(shí)候，比較當(dāng)前要彈出的數(shù)值是否等于隊(duì)列出口元素的數(shù)值，如果相等則彈出。// 同時(shí)pop之前判斷隊(duì)列當(dāng)前是否為空。void pop(int value) {if (!que.empty() && que.front() == value) {que.pop_front();}}// 如果push的數(shù)值大于入口元素的數(shù)值，那么就將隊(duì)列后端的數(shù)值彈出，直到push的數(shù)值小于等于隊(duì)列入口元素的數(shù)值為止// 這樣就保持了隊(duì)列里的數(shù)值是單調(diào)從大到小的了void push(int value) {while (!que.empty() && que.back() < value) {que.pop_back();}que.push_back(value); }int getMaxValue() {return que.front();}};
#endif
};

復(fù)雜度

見(jiàn)代碼

思路總結(jié)

• 單調(diào)隊(duì)列的特點(diǎn)：
  • 隊(duì)列頭部為隊(duì)列中元素的最大值（或最小值），且成單調(diào)遞減（或遞增）
  • 當(dāng)push元素進(jìn)隊(duì)列時(shí)，隊(duì)列中比所push元素小的需全部彈出（從尾部彈出）
  • 當(dāng)pop元素出隊(duì)列時(shí)，只有隊(duì)列頭部為需pop元素時(shí)才需pop（否則該元素已經(jīng)在push時(shí)就被彈出了）
• 實(shí)現(xiàn)單調(diào)隊(duì)列后，對(duì)數(shù)組進(jìn)行遍歷時(shí)，先將前k個(gè)元素push進(jìn)隊(duì)列；獲取一次最大值后；再?gòu)牡趉個(gè)元素起逐個(gè)遍歷數(shù)組，每遍歷一個(gè)元素獲取一次最大值。