Sliding Window Maximum Solutions in C++

// Source : https://leetcode.com/problems/sliding-window-maximum/
// Author : Hao Chen
// Date   : 2015-07-19


#include <iostream>
#include <vector>
#include <deque>
#include <set>
using namespace std;

//O(nlog(k)
vector<int> maxSlidingWindow02(vector<int>& nums, int k) {
    vector<int> result;

    //using multiset for collecting the window data (O(nlog(k) time complexity)
    multiset<int> w;

    for(int i=0; i<nums.size(); i++) {
        //remove the left item which leaves window 
        if (i >= k) {
            w.erase(w.find(nums[i-k]));
        }
        //insert the right itme which enter the window
        w.insert(nums[i]);
        if (i>=k-1) {
            result.push_back(*w.rbegin());
        }
    }

    return result;
}

//O(n)
vector<int> maxSlidingWindow01(vector<int>& nums, int k) {
    vector<int> result;

    //using multiset for collecting the window data (O(nlog(k) time complexity)
    deque<int> q;

    for(int i=0; i<nums.size(); i++) {
        //remove the left item which leaves window 
        if (!q.empty() && q.front() == i - k) {
            q.pop_front();
        }
        //remove all num which less than current number from the back one by one
        while (!q.empty() && nums[q.back()] < nums[i]) {
            q.pop_back();
        }
        //insert the right itme which enter the window
        q.push_back(i);
        if (i>=k-1) {
            result.push_back(nums[q.front()]);
        }
    }

    return result;
}

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    return maxSlidingWindow01(nums, k);
    return maxSlidingWindow02(nums, k);
}

void printVector( vector<int>& v ) {
    cout << "{ ";
    for(int i=0; i<v.size(); i++) {
        cout << v[i] << (i==v.size() ? " ": ", ");
    }
    cout << "}" << endl;
}

int main(int argc, char** argv) 
{
    int a[] = {1,3,-1,-3,5,3,6,7};
    int k = 3;
    vector<int> nums(a, a+sizeof(a)/sizeof(a[0]));
    printVector(nums);
    vector<int> result = maxSlidingWindow(nums, k);
    printVector(result);
}

/// Source : https://leetcode.com/problems/sliding-window-maximum/description/
/// Author : liuyubobobo
/// Time   : 2017-11-22

#include <iostream>
#include <vector>
#include <queue>
#include <cassert>

using namespace std;


/// Using Index Max Heap
/// Time Complexity: O(nlogn)
/// Space Complexity: O(n)

// 最大索引堆
template<typename Item>
class IndexMaxHeap{

private:
    Item *data;     // 最大索引堆中的数据
    int *indexes;   // 最大索引堆中的索引, indexes[x] = i 表示索引i在x的位置
    int *reverse;   // 最大索引堆中的反向索引, reverse[i] = x 表示索引i在x的位置

    int count;
    int capacity;

    // 索引堆中, 数据之间的比较根据data的大小进行比较, 但实际操作的是索引
    void shiftUp( int k ){

        while( k > 1 && data[indexes[k/2]] < data[indexes[k]] ){
            swap( indexes[k/2] , indexes[k] );
            reverse[indexes[k/2]] = k/2;
            reverse[indexes[k]] = k;
            k /= 2;
        }
    }

    // 索引堆中, 数据之间的比较根据data的大小进行比较, 但实际操作的是索引
    void shiftDown( int k ){

        while( 2*k <= count ){
            int j = 2*k;
            if( j + 1 <= count && data[indexes[j+1]] > data[indexes[j]] )
                j += 1;

            if( data[indexes[k]] >= data[indexes[j]] )
                break;

            swap( indexes[k] , indexes[j] );
            reverse[indexes[k]] = k;
            reverse[indexes[j]] = j;
            k = j;
        }
    }

public:
    // 构造函数, 构造一个空的索引堆, 可容纳capacity个元素
    IndexMaxHeap(int capacity){

        data = new Item[capacity+1];
        indexes = new int[capacity+1];
        reverse = new int[capacity+1];
        for( int i = 0 ; i <= capacity ; i ++ )
            reverse[i] = 0;

        count = 0;
        this->capacity = capacity;
    }

    ~IndexMaxHeap(){
        delete[] data;
        delete[] indexes;
        delete[] reverse;
    }

    // 返回索引堆中的元素个数
    int size(){
        return count;
    }

    // 返回一个布尔值, 表示索引堆中是否为空
    bool isEmpty(){
        return count == 0;
    }

    // 向最大索引堆中插入一个新的元素, 新元素的索引为i, 元素为item
    // 传入的i对用户而言,是从0索引的
    void insert(int i, Item item){
        assert( count + 1 <= capacity );
        assert( i + 1 >= 1 && i + 1 <= capacity );

        // 再插入一个新元素前,还需要保证索引i所在的位置是没有元素的。
        assert( !contain(i) );

        i += 1;
        data[i] = item;
        indexes[count+1] = i;
        reverse[i] = count+1;
        count++;

        shiftUp(count);
    }

    // 从最大索引堆中取出堆顶元素, 即索引堆中所存储的最大数据
    Item extractMax(){
        assert( count > 0 );

        Item ret = data[indexes[1]];
        swap( indexes[1] , indexes[count] );
        reverse[indexes[count]] = 0;
        reverse[indexes[1]] = 1;
        count--;
        shiftDown(1);
        return ret;
    }

    // 从最大索引堆中取出堆顶元素的索引
    int extractMaxIndex(){
        assert( count > 0 );

        int ret = indexes[1] - 1;
        swap( indexes[1] , indexes[count] );
        reverse[indexes[count]] = 0;
        reverse[indexes[1]] = 1;
        count--;
        shiftDown(1);
        return ret;
    }

    // 获取最大索引堆中的堆顶元素
    Item getMax(){
        assert( count > 0 );
        return data[indexes[1]];
    }

    // 获取最大索引堆中的堆顶元素的索引
    int getMaxIndex(){
        assert( count > 0 );
        return indexes[1]-1;
    }

    // 看索引i所在的位置是否存在元素
    bool contain( int i ){
        assert( i + 1 >= 1 && i + 1 <= capacity );
        return reverse[i+1] != 0;
    }

    // 获取最大索引堆中索引为i的元素
    Item getItem( int i ){
        assert( contain(i) );
        return data[i+1];
    }

    // 将最大索引堆中索引为i的元素修改为newItem
    void change( int i , Item newItem ){

        assert( contain(i) );
        i += 1;
        data[i] = newItem;

        shiftUp( reverse[i] );
        shiftDown( reverse[i] );
    }

    void remove(int i){

        change(i, INT_MIN);

        i += 1;

        int pos = reverse[i];
        swap( indexes[pos] , indexes[count] );
        reverse[indexes[count]] = count;
        reverse[indexes[pos]] = pos;

        shiftDown( pos );
        shiftUp( pos );

        assert(reverse[i] == count);
        reverse[i] = 0;
        count--;
    }
};


class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {

        if(k == 0 || nums.size() == 0)
            return vector<int>();

        if(k == 1)
            return nums;

        IndexMaxHeap<int> ipq(nums.size());
        for(int i = 0 ; i < k - 1 ; i ++)
            ipq.insert(i, nums[i]);

        vector<int> res;
        for(int i = k - 1 ; i < nums.size() ; i ++){
            ipq.insert(i, nums[i]);
            res.push_back(ipq.getMax());

            assert(ipq.size() == k);
            ipq.remove(i - (k - 1));
        }

        return res;
    }
};


void print_vec(const vector<int>& vec){
    for(int e: vec) cout << e << " "; cout << endl;
}

int main() {

    vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    print_vec(Solution().maxSlidingWindow(nums, 3));
    // 3 3 5 5 6 7

    return 0;
}

/// Source : https://leetcode.com/problems/sliding-window-maximum/description/
/// Author : liuyubobobo
/// Time   : 2020-04-27

#include <iostream>
#include <vector>
#include <map>
#include <cassert>

using namespace std;


/// Using Segment Tree
/// Time Complexity: O(nlogn)
/// Space Complexity: O(n)
class SegmentTree{

private:
    int n;
    vector<int> data, tree;

public:
    SegmentTree(const vector<int>& initData): data(initData), n(initData.size()), tree(4 * n){
        buildSegTree(0, 0, n - 1);
    }

    int query(int qL, int qR){
        return query(0, 0, n-1, qL, qR);
    }

private:
    void buildSegTree(int treeID, int l, int r){

        if(l == r){
            tree[treeID] = data[l];
            return;
        }

        int mid = (l + r) / 2;
        buildSegTree(treeID * 2 + 1, l, mid);
        buildSegTree(treeID * 2 + 2, mid + 1, r);
        tree[treeID] = max(tree[treeID * 2 + 1], tree[treeID * 2 + 2]);
        return;
    }

    int query(int treeID, int treeL, int treeR, int qL, int qR){

        if(treeL > qR || treeR < qL) return 0;

        if(qL <= treeL && qR >= treeR)
            return tree[treeID];

        int mid = (treeL + treeR) / 2;
        int leftRes = query(2 * treeID + 1, treeL, mid, qL, qR);
        int rightRes = query(2 * treeID + 2, mid + 1, treeR, qL, qR);
        return max(leftRes, rightRes);
    }
};

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {

        if(k == 0 || nums.size() == 0)
            return vector<int>();

        if(k == 1) return nums;

        SegmentTree segmentTree(nums);
        vector<int> res;
        for(int i = k - 1 ; i < nums.size() ; i ++)
            res.push_back(segmentTree.query(i - (k - 1), i));

        return res;
    }
};


void print_vec(const vector<int>& vec){
    for(int e: vec) cout << e << " "; cout << endl;
}

int main() {

    vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    print_vec(Solution().maxSlidingWindow(nums, 3));
    // 3 3 5 5 6 7

    return 0;
}

/// Source : https://leetcode.com/problems/sliding-window-maximum/description/
/// Author : liuyubobobo
/// Time   : 2020-04-27

#include <iostream>
#include <vector>
#include <map>
#include <cassert>

using namespace std;


/// Using a map as a priority queue
/// Time Complexity: O(nlogn)
/// Space Complexity: O(n)
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {

        if(k == 0 || nums.size() == 0)
            return vector<int>();

        if(k == 1) return nums;

        map<int, int> window;
        for(int i = 0; i < k - 1; i ++)
            window[nums[i]] ++;

        vector<int> res;
        for(int i = k - 1 ; i < nums.size() ; i ++){

            window[nums[i]] ++;
            res.push_back(window.rbegin()->first);

            window[nums[i - k + 1]] --;
            if(window[nums[i - k + 1]] == 0) window.erase(nums[i - k + 1]);
        }

        return res;
    }
};


void print_vec(const vector<int>& vec){
    for(int e: vec) cout << e << " "; cout << endl;
}

int main() {

    vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    print_vec(Solution().maxSlidingWindow(nums, 3));
    // 3 3 5 5 6 7

    return 0;
}

/// Source : https://leetcode.com/problems/sliding-window-maximum/description/
/// Author : liuyubobobo
/// Time   : 2017-11-22

#include <iostream>
#include <vector>
#include <deque>
#include <cassert>

using namespace std;


/// Using Deque as a Decreasing Queue
/// It's a template problem! :)
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {

        if(k == 0 || nums.size() == 0)
            return vector<int>();

        if(k == 1)
            return nums;

        deque<int> q;
        vector<int> res;
        for(int i = 0 ; i < nums.size() ; i ++){

            while(!q.empty() && q.back() < nums[i])
                q.pop_back();
            q.push_back(nums[i]);

            if(i >= k - 1){
                res.push_back(q.front());
                if(q.front() == nums[i - (k - 1)])
                    q.pop_front();
            }
        }

        return res;
    }
};


void print_vec(const vector<int>& vec){
    for(int e: vec) cout << e << " "; cout << endl;
}

int main() {

    vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    print_vec(Solution().maxSlidingWindow(nums, 3));
    // 3 3 5 5 6 7

    return 0;
}

/// Source : https://leetcode.com/problems/sliding-window-maximum/description/
/// Author : liuyubobobo
/// Time   : 2019-03-09

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;


/// Dynamic Programming
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {

        int n = nums.size();

        if(k == 0 || n == 0)
            return vector<int>();

        if(k == 1)
            return nums;

        vector<int> right(n);
        int cur = nums[0];
        for(int i = 0; i < n; i ++){
            if(i % k == 0) cur = nums[i];
            else cur = max(cur, nums[i]);
            right[i] = cur;
        }

        vector<int> left(n);
        cur = nums[n - 1];
        for(int i = n - 1; i >= 0; i --){
            if(i % k == k - 1) cur = nums[i];
            else cur = max(cur, nums[i]);
            left[i] = cur;
        }

        vector<int> res(n - k + 1);
        for(int i = 0; i <= n - k; i ++)
            res[i] = max(left[i], right[min(i + k - 1, n - 1)]);

        return res;
    }
};


void print_vec(const vector<int>& vec){
    for(int e: vec) cout << e << " "; cout << endl;
}

int main() {

    vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    print_vec(Solution().maxSlidingWindow(nums, 3));
    // 3 3 5 5 6 7

    return 0;
}