1438. 绝对差不超过限制的最长连续子数组（滑动窗口——multiset的使用）

给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。

如果不存在满足条件的子数组，则返回 0 。

示例 1：

输入：nums = [8,2,4,7], limit = 4
输出：2
解释：所有子数组如下：
[8] 最大绝对差 |8-8| = 0 <= 4.
[8,2] 最大绝对差 |8-2| = 6 > 4.
[8,2,4] 最大绝对差 |8-2| = 6 > 4.
[8,2,4,7] 最大绝对差 |8-2| = 6 > 4.
[2] 最大绝对差 |2-2| = 0 <= 4.
[2,4] 最大绝对差 |2-4| = 2 <= 4.
[2,4,7] 最大绝对差 |2-7| = 5 > 4.
[4] 最大绝对差 |4-4| = 0 <= 4.
[4,7] 最大绝对差 |4-7| = 3 <= 4.
[7] 最大绝对差 |7-7| = 0 <= 4.
因此，满足题意的最长子数组的长度为 2 。

分析：

题目主要是求连续满足条件的最长子区间，滑动窗口类型的题，要能实时得到并更新新窗口的最大最小值，起初想到了优先队列，但是只能得到最大值，小顶堆的实现又比较麻烦，参考了别的思路，学到了利用multiset的特性来解决这类动态区间的极值问题。

multiset：

1. 集合中元素相比set来说是可以重复的
2. insert后的元素在集合中是自动排好序的（依赖multiset底层的红黑树实现）
3. 可以通过multiset.begin()和multiset.rbegin()来得到集合两端的值，即最小值和最大值

测试用例：

• 对multiset插入无序的元素，可以看到集合已经自动从小到大排列好

• 每次对multiset插入后的集合调用函数，可以直接得到最小值和最大值

cout << "当前集合中的最小值:" << *st.begin() << " 当前集合中的最大值:" << *st.rbegin() << endl;

题目代码：

#include<set>
class Solution {
    
public:int longestSubarray(vector<int>& nums, int limit) {
    multiset<int> st;int left = 0, right = 0;int maxLength = 0;while (right < nums.size()){
    st.insert(nums[right]);//for(int x : st) cout << x << " " ;//cout << "当前集合中的最小值:" << *st.begin() << " 当前集合中的最大值:" << *st.rbegin() << endl;while(*st.rbegin() - *st.begin() > limit){
    //cout << *st.find(nums[left]) << endl;// 窗口中有不符合的了，但不知道这个元素在nums的位置，只能从左向右擦st.erase(st.find(nums[left])); // erase擦除的是值对应的地址，想打印值加上*，如上句所示left++;}maxLength = max(maxLength, right - left + 1);right++;}return maxLength;}
};