leetcode 1438. 绝对差不超过限制的最长连续子数组----双指针篇3，滑动窗口篇2

class Solution {
public:
	int longestSubarray(vector<int>& nums, int limit) 
	{
		if (nums.empty()) return 0;
		if (nums.size() == 1) return 1;
		int maxLen = 0;
		for (int i = 0; i < nums.size()-1; i++)
		{
			for (int j = 1; j < nums.size(); j++)
			{
				//如果从当前i开始到j结束的连续子数组中出现了绝对差大于限制值的，那么再往后面继续扩大子数组范围也没有意义了
				//found标志记录当前子数组里面有么有任意两个元素的绝对值之差不满足条件
				bool found = false;
				for (int k = i; k < j; k++)
				{
					//一旦找到了一对不满足的例子，就设置标志为真，然后退出当前循环
					if (abs(nums[j] - nums[k]) > limit)
					{
						found = true;
						break;
					}
				}
				//如果找到了不满足的例子，那么从当前i开始的连续子数组就不需要继续往后面扩充长度了，直接从下一个i开始找子数组
				if (found)
					break;
				//能够走到这里说明当前连续子数组满足条件
				maxLen = max(maxLen, j - i+1);
			}
		}
		return maxLen;
	}
};

class Solution {
	map<int, int> m;//关键之是当前元素的值，值是当前元素的出现次数
public:
	int longestSubarray(vector<int>& nums, int limit) 
	{
		if (nums.empty()) return 0;
		if (nums.size() == 1) return 1;
		int maxLen = 0;
		int i = 0;//i指针指向滑动窗口的左端
		for (int j = 0; j < nums.size(); j++)//j指针指向滑动窗口的右端
		{
			m[nums[j]]++;//一开始为0，加1后为1，表示当前元素出现过了一次
			//当前滑动窗口内的最大元素值减去最小元素值不满足条件
			if (m.rbegin()->first - m.begin()->first > limit)
			{
				//将i指针指向的滑动窗口最左端的元素移出

				//这里先将当前元素出现次数减去一，因为这里可能有重复元素
				m[nums[i]]--;
				//判断当前元素的出现次数是否为0，为0的话，直接从map容器中删除
				if (m[nums[i]] == 0)
				{
					//将保存再map容器中的滑动窗口最左端的值删除
					m.erase(nums[i]);
				}
				//i指针往右移动一格，表明将最左端的元素移出窗口
				i++;
			}
			//计算当前滑动窗口的最大长度
			maxLen = max(maxLen, j - i + 1);
		}
		return maxLen;
	}
};

class Solution {
	multiset<int> s;//将当前元素的值保存到set容器中
public:
	int longestSubarray(vector<int>& nums, int limit) 
	{
		if (nums.empty()) return 0;
		if (nums.size() == 1) return 1;
		int maxLen = 0;
		int i = 0;//i指针指向滑动窗口的左端
		for (int j = 0; j < nums.size(); j++)//j指针指向滑动窗口的右端
		{
			s.insert(nums[j]);
			if (*s.rbegin() - *s.begin() > limit)
			{
				s.erase(s.find(nums[i]));
				i++;
			}
			//计算当前滑动窗口的最大长度
			maxLen = max(maxLen, j - i + 1);
		}
		return maxLen;
	}
};

	multiset<int> set;
	set.insert(1);
	set.insert(4);
	set.insert(3);
	set.insert(2);
	set.insert(5);
	set.insert(3);
	for_each(set.begin(), set.end(), [](int cal) {cout << cal << " "; });
	cout << endl;
	set.erase(3);
	for_each(set.begin(), set.end(), [](int cal) {cout << cal << " "; });

s.erase(s.find(nums[i]));

class Solution {
	deque<int> Min;//单调增队列
	deque<int> Max;//单调减队列
public:
	int longestSubarray(vector<int>& nums, int limit) 
	{
		if (nums.empty()) return 0;
		if (nums.size() == 1) return 1;
		int maxLen = 0;
		int i = 0, j = 0;
		while (j < nums.size())
		{
			int num = nums[j];//获取当前要加入滑动窗口的元素
			while (!Min.empty() && Min.back() > num)
				Min.pop_back();
			Min.push_back(num);
			while (!Max.empty() && Max.back() < num)
				Max.pop_back();
			Max.push_back(num);
			//让滑动窗口左端指针移动到当前滑动窗口内的子数组满足题目要求为止
			while (Max.front() - Min.front() > limit)
			{
                //这里我们需要把左端指针i移动到最大值和最小值两者中下标靠前的后面一个为止即可
				//并且将对应下标靠前的那个从对应的队列首元素中移出
				if (nums[i] == Max.front())
					Max.pop_front();
				else if (nums[i] == Min.front())
					Min.pop_front();
					i++;
			}
			maxLen = max(maxLen, j - i + 1);
			j++;
		}
		return maxLen;
	}
};

//判断当前i指向位置的元素是否是当前滑动窗口内的最大值或者最小值，如果是就将其从对应的队列中移出即可

class Solution {
	deque<int> Min;//单调增队列
	deque<int> Max;//单调减队列
public:
	int longestSubarray(vector<int>& nums, int limit) 
	{
		if (nums.empty()) return 0;
		if (nums.size() == 1) return 1;
		int maxLen = 0;
		int i = 0, j = 0;
		while (j < nums.size())
		{
			int num = nums[j];//获取当前要加入滑动窗口的元素
			while (!Min.empty() && Min.back() > num)
				Min.pop_back();
			Min.push_back(num);
			while (!Max.empty() && Max.back() < num)
				Max.pop_back();
			Max.push_back(num);
			if (Max.front() - Min.front() > limit)
			{
				//判断当前i指向位置的元素是否是当前滑动窗口内的最大值或者最小值，如果是就对应的队列中移出即可
				if (nums[i]==Max.front())
					Max.pop_front();
				else if(nums[i]==Min.front())
					Min.pop_front();
					i++;
			}
			maxLen = max(maxLen, j - i + 1);
			j++;
		}
		return maxLen;
	}
};