面试必刷算法TOP101之限流算法(定长滑动窗口)问题 TOP18_leecode 如果窗口中不存在则置顶,如果存在则将该数字移动到顶端

上一篇介绍的也是滑动窗口详细请看这里，窗口是不断变化的，这里介绍的定长滑动窗口，窗口大小固定不变的。
这里还是用一套思想解决这一类问题思路如下：
定长窗口是不需要收敛的，因为长度固定，当窗口达到条件时，begin然后收缩一次窗口，end也往后移动一位为了保存窗口的大小不变，然后重复直到到达数组或者字符串的尾部。

存在重复元素 II

题目来源：leetcode
1、题目描述
给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。
2、思路解析
使用hash来存放数据，先开始end右移扩大窗口，同时判断hash中是不是存在后边数据如果没有直接存到hash中，当end扩大到k后就先删除窗口前边的数据，同时判断新来的数据在hash是不是存在，没有存在就存放新来的数据，如果存在就直接返回true，因为前边窗口控制已经达到条件k了后边就不在操心后边的条件了
3、代码实现

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        if(nums.empty()){
            return false;
        }
        unordered_set<int> s;
        int begin=0;
        for(int end=0;end<nums.size();end++){          
            if(end-begin>k){             
                 //没有满足条件的缩小窗口
                //长度不满足条件删除数据
                s.erase(nums[begin++]);
            }
            //这里找到符合窗口长度，接下来这是不是数据是不是在前边出现过的数据
            if(s.count(nums[end])){
                //前边数据中存在符合条件的
                return true;
            }
            //没有找到前边出现的数据，但是只符合一半条件
            s.insert(nums[end]);
        }
return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

存在重复元素 Ⅲ

题目来源：leetcode
1、问题描述
给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。
如果存在则返回 true，不存在返回 false。
2、思路如下：
思路一：滑动窗口+暴力破解
先开始end右移扩大窗口，当窗口达到k时begin和end一起往后移动直到移动到数组尾部，但是满足另一个条件就是双循环判断区间内是不是存在abs(nums[i] - nums[j]) <= t ，但是因为时间复杂度为O(Nk^2)时间复杂度太大。
思路二：滑动窗口+新来数据检查
先开始end右移扩大窗口，当窗口达到k时begin和end一起往后移动直到移动到数组尾部，当来一个新数据时就和每个窗口内元素做减法运算当达到abs(nums[i] - nums[j]) <= t 但是时间复杂度还是O(NK)
思路三：滑动窗口+二分法
right 指针每次后移，如果发现 set 的大小大于 k ，则需要把 nums[begin] 从 set 中删除；
查找 set 中是否有大于等于 nums[end] - t 的元素，如果有的话，说明在大小不超过为 k 的窗口内有绝对值差小于等于 t 的两个元素，返回 true。
如果把 nums 遍历了一遍仍然没有结果，则返回 false。
前边还是一样但是在判断另一个条件时是不一样了因为要找区间符合abs(nums[i] - nums[j]) <= t，所以每次来了新数据就先求abs(nums[end]-t)然后在数组中寻找大于等于这个条件的即可
3、代码实现

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
   
        long begin=0;
        long end=1;
        set<long>v;
        v.insert(nums[0]);
        for(;end<nums.size();end++){
          
           if(end-begin>k){
                //窗口大小不符合
                //修改窗口大小
                v.erase(nums[begin]);
                begin++;
            }
            //符合窗口大小
             //判断新来的数据是不hi是差值符合条件不符合就插入到数组
             for(int i=0;i<v.size();i++){
                 if(abs(nums[end]-v[i])<=t){
                     return true;
                 }
             }
          
           
            v.insert(nums[end]);
        }
        return false;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

算法改进

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
   
        long begin=0;
        long end=1;
        set<long>v;
        v.insert(nums[0]);
        for(;end<nums.size();end++){
          
           if(end-begin>k){
                //窗口大小不符合
                //修改窗口大小
                v.erase(nums[begin]);
                begin++;
            }
             auto iter = v.lower_bound((long)nums[end] - t);//nums[end]-nums[i]<=t
                                                            //nums[end]-t<=nums[i]
                                                            //现在只需找到符合在数据中nums[i]即可
                        
            if (iter != v.end() &&abs(*iter-nums[end])<=t) {
                //在数据中找到并且满足条件
                return true;
            }  
            //不满足条件将数据插入到数组中
            v.insert(nums[end]);
        }
        return false;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

滑动窗口最大值

题目来源：Leetcode
1、问题描述
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
2、思路解析
优先级队列+topK
先将数组的前个数据放入到队列中然后将队列中的对顶元素删除，接着再次插入数据到队列直到到达数据尾部
滑动窗口+双端队列
利用双端队列记录当前滑动窗口的元素索引
队头记录滑动窗口中最大元素的索引
队列中存放的元素索引对应的是递减的，就是说队头元素就是区间内最大的元素，队列中元素索引对应元素是递减的
遍历数组：

• 如果队列最左侧索引已不在滑动窗口范围内，弹出队列最左侧索引
• 通过循环确保队列的最左侧索引所对应元素值最大
• 新元素入队
• 从第一个滑动窗口的末尾索引开始将最大值存储到结果v中

先形成大小为k的窗口

队头元素入数组，窗口后移，检测对头元素是不是在区间内，没有就删除对头元素。接下来拿队尾元素和区间内新来元素比较，没有新来元素大就删除队尾元素，直到碰到比新来数据大的元素或者队列为空，接下来插入到将新来元素插入到队列的后边。

3、代码实现

class Solution {
     private:
     vector<int>Max;
public:
  vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    priority_queue<pair<int,int>> q;
    vector<int> v;
    int begin = 0;

    for (;begin < k;begin++) {
        q.push(make_pair(nums[begin],begin));
    }
    v.push_back(q.top().first);
 
    for (int i=k;i < nums.size();i++) {
        //先去堆顶元素
        
        q.push(make_pair(nums[i], i));
        while (q.top().second <= i - k) { 
            q.pop(); 
        }
        v.push_back(q.top().first);
       
    }

    return v;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
     private:
     vector<int>Max;
public:
  vector<int> maxSlidingWindow(vector<int>& nums, int k) {
   vector<int> v;
	deque<int> q;
	int begin = 0;
	int end = 1;
	q.push_back(begin);
	for (;end <= nums.size();end++) {
		//窗口判断
		if (end - begin + 1 > k) {
			//窗口位置取出对头元素
			v.push_back(nums[q.front()]);	
			begin++;
		}
		//判断队头元素是不是在区间中
		if (!q.empty() && q.front() <begin) {
			q.pop_front();
		}
		 while (!q.empty()&& nums[q.back()] < nums[end]) {
			//判断队尾元素是不是大于信赖元素
			//比新来元素小就删除
				q.pop_back();
			}
			//将数据添加窗口中
			q.push_back(end);
		
		}
	
	return v;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35