哈希表应用（map,set共同作用）

码蹄集OJ-区间最大值

#include<bits/stdc++.h> 
using namespace std;
map<int,int>m;
set<int>s;
int main( )
{int n,k;cin>>n>>k;int arr[n];for(int i=0;i<n;i++){cin>>arr[i];}for(int i=0;i<k;i++){m[arr[i]]++;}for(int i=0;i<k;i++){if(m[arr[i]]==1){s.insert(arr[i]);}}if(s.empty()){cout<<"-1 ";}else{cout<<*s.rbegin()<<" ";}for(int i=k;i<n;i++){if(m[arr[i-k]]==1){s.erase(arr[i-k]);}if(m[arr[i-k]]==2){s.insert(arr[i-k]);}m[arr[i-k]]--;if(m[arr[i]]==0){s.insert(arr[i]);}if(m[arr[i]]==1){s.erase(arr[i]);}m[arr[i]]++;if(s.empty()){cout<<"-1 ";}else{cout<<*s.rbegin()<<" ";}}return 0;
}

map<int,int>m是 一个把整数映射到整数的、自动排序的字典。

键与值的类型都为int,键指的是数字，值指的是数字出现的个数。

set<int>s是 一个只存整数、自动去重并自动升序排序的集合。

这道题就是将滑动窗口大小为k的数字与个数存入map中，再将map中值为1的数字存入set中。

输出：在set为空时输出-1，在不为空时输出：

        cout<<*s.rbegin()<<" ";

接下来的问题就是如何实现这个滑动窗口，先将0到k的数字和个数存入map中，再通过向后滑动判断出去的数字与进入的数字，根据不同情况更改set中的值，但别忘了判断结束后也要更改map中的值。