LeetCode 1438. 绝对差不超过限制的最长连续子数组（滑动窗口,单调队列/map,set）

思路：

解法1和解法2参考了leetcode题解，主要是参考码风。解法3是博主自己写的，效率相对不高。

解法1：

• 双指针维护滑动窗口，使用两个单调队列记录当前区间最大值最小值
  双指针维护这个窗口，要判断其是否合理需要记录最大值最小值，可以想到用单调队列。但是如何用一个双指针维护两个队列呢？
• 窗口扩大好办，就是一直右移右指针。而窗口缩小的时候，实际上只需要考虑极值，要么是删掉最大值单调队列的头指针，要么是删掉最小值单调队列的头指针。所以左移左指针的时候，只要其中一个单调队列队首和左指针数字相同，那就弹出。

class Solution {
public:int longestSubarray(vector<int>& nums, int limit) {deque<int>mx_q,mi_q;int l = 0,r = 0,n = nums.size();int ans = 0;while(r < n) {while(!mx_q.empty() && nums[r] > mx_q.back()) mx_q.pop_back();while(!mi_q.empty() && nums[r] < mi_q.back()) mi_q.pop_back();mi_q.push_back(nums[r]);mx_q.push_back(nums[r]);r++;while(mx_q.front() - mi_q.front() > limit) {if(mx_q.front() == nums[l]) mx_q.pop_front();if(mi_q.front() == nums[l]) mi_q.pop_front();l++;}ans = max(ans,r - l);}return ans;}
};

解法2： map+滑动窗口
这个就应该不用多说了，multiset也可以维护。

class Solution {
public:int longestSubarray(vector<int>& nums, int limit) {map<int,int>mp;int l = 0,r = 0;int ans = 0;while(r < nums.size()) {mp[nums[r]]++;while(mp.rbegin() -> first - mp.begin() -> first > limit) {mp[nums[l]]--;if(mp[nums[l]] == 0) {mp.erase(nums[l]);}l++;}ans = max(ans,r - l + 1);r++;}return ans;}
};

解法3： 二分+滑动窗口
因为学滑动窗口的时候就记住了这个可以用来维护k大小区间的最值。
所以想到二分子数组长度，然后用滑动窗口$check$，复杂度$O(nlog(n))$

class Solution {
public:vector<pair<int,int>>q1,q2; //id vint l1,r1,l2,r2;void solve1(vector<int>&nums,int id,int mid) { //最大值，递减队列while(l1 <= r1 && q1[r1].first - q1[l1].first >= mid - 1) l1++;while(l1 <= r1 && q1[r1].second < nums[id]) r1--;q1[++r1] = {id,nums[id]};}void solve2(vector<int>&nums,int id,int mid) { //最小值，递增队列while(l2 <= r2 && q2[r2].first - q2[l2].first >= mid - 1) l2++;while(l2 <= r2 && q2[r2].second > nums[id]) r2--;q2[++r2] = {id,nums[id]};}bool check(vector<int>&nums,int mid,int limit) {q1.resize(nums.size());q2.resize(nums.size());l1 = l2 = 0;r1 = r2 = -1;for(int i = 0;i < nums.size();i++) {solve1(nums,i,mid);solve2(nums,i,mid);if(i >= mid - 1) {int mx = q1[l1].second;int mi = q2[l2].second;if(mx - mi <= limit) return true;}}return false;}int longestSubarray(vector<int>& nums, int limit) {int n = nums.size();int l = 1,r = n,ans = 0;while(l <= r) {int mid = (l + r) >> 1;if(check(nums,mid,limit)) {ans = mid;l = mid + 1;} else {r = mid - 1;}}return ans;}
};