雙端隊列

Number of Subarrays with Bounded Maximum

Sliding Window Maximum

技巧:

1. 雙端隊列可以操作隊首與隊尾
2. 隊列中保存數組的下標

Number of Subarrays with Bounded Maximum

題意: 給一個正整數的數組nums, 求出連續非空子序列的最大值在[L, R]中的個數

A = [2, 1, 4, 3]L = 2R = 3return 3; // 解釋 [2], [2,1], [3]

觀察:

1. 如果num[i] > R, 意味著後面的子序列將被分割: ), 我們就可以清空雙端隊列，隊列前面保存的數據沒有保存的意義了
2. 如果nums[i] < L
1. 如果是首次出現，需要記錄在雙端隊列里，因為和後續任意一個屬於[L, R]的數都可以構成滿足條件的子序列；
2. 如果不是首次出現就沒必要記錄在雙端隊列里，如果隊列尾的數在[L, R]區間，就需要更新ans，如果隊列尾的數不在[L, R]區間，那麼隊列尾部的數必然小於L，此時意味著隊列中沒有數在[L, R]區間, 也就沒必要更新ans;
3. 時，ans++, 如果隊列存在數字，意味著當前的數可以和前面任意的數字構成滿足條件的序列，因為隊列只會存下 <= R的數的下標

class Solution {public: int numSubarrayBoundedMax(vector<int>& nums, int L, int R) { int n = nums.size(), ans = 0; deque<int> p; for (int i=0; i < n; i++) { if (nums[i] < L) { if (!p.empty()) { if (nums[p.back()] >= L && nums[p.back()] <= R) ans += (p.back() - p.front() + 1); } else p.push_back(i); } else if (nums[i] > R) { while (!p.empty()) p.pop_back(); } else { ans += 1; if (!p.empty()) ans += i - p.front(); p.push_back(i); } } return ans; }};

Sliding Window Maximum

題意: 求滑動窗口的最大值

nums = [1,3,-1,-3,5,3,6,7], k = 3Window position Max--------------- -----[1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7

思路:

1. 只有最大數對我們有意義，我們的隊列需要記錄最大數的下標
2. 如果當前的數比隊尾的數大，則需要從隊尾中彈出
3. 如果當前的數的下標與隊首的下標相差k, 則需要從堆首中彈出

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

推薦閱讀：