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

題目描述

給定一個(gè)數(shù)組和滑動(dòng)窗口的大小，請(qǐng)找出所有滑動(dòng)窗口里的最大值。

例如，如果輸入數(shù)組 [2,3,4,2,6,2,5,1]
及滑動(dòng)窗口的大小 3
，那么一共存在 6
個(gè)滑動(dòng)窗口，它們的最大值分別為 [4,4,6,6,6,5]

注意：
數(shù)據(jù)保證 k大于 0，且 k小于等于數(shù)組長度。
數(shù)據(jù)范圍
數(shù)組長度 [1,1000]

樣例
輸入：[2, 3, 4, 2, 6, 2, 5, 1] , k=3
輸出: [4, 4, 6, 6, 6, 5]

思路

模擬窗口的滑動(dòng)
當(dāng)窗口里有k個(gè)元素的時(shí)候， 向后滑動(dòng)

• 檢查窗口內(nèi)元素是否合法
• 窗口的一端納入一個(gè)元素
• 窗口的另一端移除一個(gè)元素

由于符合先進(jìn)先出的原則，所以可以用隊(duì)列來模擬窗口
然后進(jìn)一步挖掘性質(zhì)：

假設(shè)公司里有一群?jiǎn)T工， 現(xiàn)在來了一個(gè)新員工A， 如果員工A的能力出眾， 并且年紀(jì)小， 那么

1. A可以替換掉所有員工中能力小于等于A的員工
2. A可以替換掉所有員工中年齡小于等于A的員工

能力->本題的數(shù)值
年齡->本題的索引

那么：

1. 為什么上面的性質(zhì)合理呢？
   因?yàn)榛瑒?dòng)窗口需要的是最大值，所以，只要當(dāng)前元素大于隊(duì)列中元素，那么隊(duì)列中元素就不需要了
2. 為什么可以取等？
   因?yàn)閮蓚€(gè)數(shù)值一樣的元素并列， 例如int a[3] = {1, 1, 1};, a數(shù)組里三個(gè)元素均相等，那么當(dāng)需要最大值的時(shí)候
   取a[2]一定沒錯(cuò)， 因?yàn)槿绻祷豠[0]， 那么窗口移動(dòng)以后，a[0]會(huì)被移除，a[1]同理

也就是說，a[2]活到了最后

所以：
最終隊(duì)列會(huì)形成一個(gè)遞減序列， 因此， 隊(duì)頭元素就是最大值
每次從隊(duì)頭里獲取最大值，放入到結(jié)果數(shù)組中

代碼

class Solution {
public:vector<int> maxInWindows(vector<int>& nums, int k) {vector<int> res;deque<int> q;for (int i = 0; i < nums.size(); i ++ ){if (q.size() && i - q.front() >= k) q.pop_front();while (q.size() && nums[q.back()] <= nums[i]) q.pop_back();q.push_back(i);if (i >= k - 1) res.push_back(nums[q.front()]);}return res;}
};