## Saturday, July 18, 2015

### LeetCode OJ - Sliding Window Maximum

Problem:

Solution:

My first thought is to have a priority queue model the sliding window, that allows me to find the maximum quickly, delete quickly in $O(log n)$, and insert quickly in $O(log n)$.

The problem stretched me to look for a linear algorithm, I did look at one hint about maximum stack, and then I come up with this solution.

The key idea is that the sliding window is a queue. So if I have a data structure that can do enqueue, dequeue and maximum all in $O(1)$ time, then we are done.

The maximum stack can do that, but that is a stack.

But recall I have done a problem to simulate a queue using a stack, so that's it. Use two maximum stack to simulate a maximum queue!

Code:

#include "stdafx.h"

// https://leetcode.com/problems/sliding-window-maximum/

#include "LEET_SLIDING_WINDOW_MAXIMUM.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

namespace _LEET_SLIDING_WINDOW_MAXIMUM
{
class Solution
{
private:
vector<int> max_queues_val;
vector<int> max_queues_max;
int size;
int stack1_top;
int stack2_top;

void initialize_queues(int size)
{
this->size = size;
this->stack1_top = 0;
this->stack2_top = size - 1;
this->max_queues_max.resize(size);
this->max_queues_val.resize(size);
}

void enqueue(int val)
{
push1(val);
}

int queue_max()
{
if (this->size1() == 0)
{
return this->max2();
}
else if (this->size2() == 0)
{
return this->max1();
}
else
{
return max(this->max1(), this->max2());
}
}

int dequeue()
{
if (this->size2() == 0)
{
while (this->size1() > 0)
{
this->push2(this->pop1());
}
}
return this->pop2();
}

int size1()
{
return this->stack1_top;
}

void push1(int val)
{
this->max_queues_val[this->stack1_top] = val;
if (this->stack1_top == 0)
{
this->max_queues_max[this->stack1_top] = val;
}
else
{
this->max_queues_max[this->stack1_top] = max(val, max1());
}
this->stack1_top++;
}

int pop1()
{
this->stack1_top--;
return this->max_queues_val[this->stack1_top];
}

int max1()
{
return this->max_queues_max[this->stack1_top - 1];
}

int size2()
{
return this->size - 1 - this->stack2_top;
}

void push2(int val)
{
this->max_queues_val[this->stack2_top] = val;
if (this->stack2_top == this->size - 1)
{
this->max_queues_max[this->stack2_top] = val;
}
else
{
this->max_queues_max[this->stack2_top] = max(val, max2());
}
this->stack2_top--;
}

int pop2()
{
this->stack2_top++;
return this->max_queues_val[this->stack2_top];
}

int max2()
{
return this->max_queues_max[this->stack2_top + 1];
}

public:
vector<int> maxSlidingWindow(vector<int>& nums, int k)
{
vector<int> result;
if (nums.size() == 0)
{
return result;
}
initialize_queues(k);
for (int i = 0; i < k; i++)
{
this->enqueue(nums[i]);
}

for (unsigned int i = k; i < nums.size(); i++)
{
result.push_back(this->queue_max());
this->dequeue();
this->enqueue(nums[i]);
}
result.push_back(this->queue_max());
return result;
}
};
};

using namespace _LEET_SLIDING_WINDOW_MAXIMUM;

int LEET_SLIDING_WINDOW_MAXIMUM()
{
Solution solution;
int case1[] = { 1,3,-1,-3,5,3,6,7 };
vector<int> case1_result = solution.maxSlidingWindow(vector<int>(case1, case1 + _countof(case1)), 3);
for (unsigned int i = 0; i < case1_result.size(); i++) { cout << case1_result[i] << ", "; } cout << endl;
return 0;
}