Sliding Window

C++

1vector<int> maxSlidingWindow(vector<int>& nums, int k) {
2    multiset<int> s;
3    vector<int> ret;
4    for(int i = 0; i < k; i++){
5        s.insert(nums[i]);
6    }
7    for(int i = k; i < nums.size(); i++){
8        ret.push_back(*s.rbegin());
9        s.erase(s.find(nums[i-k]));
10        s.insert(nums[i]);

Java

1static TreeMap<Integer, Integer> multiset = new TreeMap<Integer, Integer>();
2static void add(int x) {
3    if(multiset.containsKey(x)) {
4        multiset.put(x, multiset.get(x) + 1);
5    } else {
6        multiset.put(x, 1);
7    }
8}
9static void remove(int x) {
10    multiset.put(x, multiset.get(x) - 1);

C++

1int n;
2set<int> s;
3int a[200000], ans;
4
5int main() {
6    int r = -1;
7    cin >> n; F0R(i,n) cin >> a[i];
8    F0R(i,n) {
9        while (r < n-1 && !s.count(a[r+1])) s.insert(a[++r]);
10        ans = max(ans,r-i+1);

Java

1public class test{
2    public static void main(String[] args) throws Exception {
3        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
4        int n = Integer.parseInt(br.readLine());
5        StringTokenizer st = new StringTokenizer(br.readLine());
6        int a[] = new int[n];
7        for (int i = 0; i < n; i++) a[i] = Integer.parseInt(st.nextToken());
8        int r = -1;
9        HashSet<Integer> s = new HashSet<Integer>();
10        int ans = 0;

C++

1vector<int> maxSlidingWindow(vector<int>& nums, int k) {
2    deque<int> d;
3    vector<int> ret;
4    for(int i = 0; i < k; i++){
5        while(!d.empty() && nums[i] > nums[d.back()]){
6            d.pop_back();
7        }
8        d.push_back(i);
9    }
10    for(int i = k; i < nums.size(); i++){

Java

1static ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {
2    ArrayList<Integer> ret = new ArrayList<Integer>();
3    ArrayDeque<Integer> d = new ArrayDeque<Integer>();
4    for (int i = 0; i < k; i++) {
5        while(!d.isEmpty() && nums[i] > nums[d.peekLast()]) {
6                d.pollLast();
7        }
8        d.addLast(i);
9    }
10    for (int i = k; i < nums.length; i++) {