~/leetcode $ 239. Sliding Window Maximum

Initial thoughts after reading this question, the brute force approach is rather simple: iterate through all the elements in the current window and append the max element found. However, given that this question is a ‘Hard’, it can’t be this easy type shi

Yep, tested the brute force method, it didn’t work. Brute force solution code:

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int startingIndex = 0;
        vector<int> ans;
        while (startingIndex + k <= nums.size()) {
            int max_element = std::numeric_limits<int>::min();
            for (int i = startingIndex; i < startingIndex + k; ++i) {
                if (nums[i] > max_element) {
                    max_element = nums[i];
                }
            }
            ans.push_back(max_element);
            ++startingIndex;
        }

        return ans;
    }
};

Next idea, have some kind of list that contains the maximum element for that window (because this would make it a lot easier to just append whatever is the ‘current max’ contained in this list. After thinking about it for over 15 minutes, I think I have some plans of an idea.

There’s a few things to notice here:

1. Inside of any window, any numbers that are between two larger numbers is irrelevant to our solution: e.g. if we have [8, 3, 6], 3 will never be considered the max because of the 4 and the 6.
2. This means that when we want to keep track of the largest numbers in the current window, it will always be in ascending order: e.g. for [8, 3, 6], we only need to keep track of [8, 6]

With these two facts, we can reach a conclusion of using a monotonic queue in ascending order, where we pop from the front and append from the back every time we want to slide our window. When we pop a element that is in the monotonic queue, we will pop it from the monotonic queue as well. Else, we leave it alone. When we append from the back, we ensure that the monotonic nature of the queue is maintained by ensuring removing elements that are smaller than the appended element from the monotonic queue.

Once the sliding is done, we can append the front of the monotonic queue to the answer vector and return it.

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ans;
        if (nums.size() == 0) return ans;

        // set up the window
        deque<int> d;
        d.push_back(nums[0]);
        for (int i = 1; i < k; ++i) {
            if (nums[i] < d.back()) {
                d.push_back(nums[i]);
            } else {
                while (!d.empty() && d.back() < nums[i]) {
                    d.pop_back();
                }
                d.push_back(nums[i]);
            }
        }
        ans.push_back(d.front());

        // move the window
        for (int i = k; i < nums.size(); ++i) {
            int popped = nums[i - k];
            if (d.front() == popped) {
                d.pop_front();
            }

            if (nums[i] < d.back()) {
                d.push_back(nums[i]);
            } else {
                while (!d.empty() && d.back() < nums[i]) {
                    d.pop_back();
                }
                d.push_back(nums[i]);
            }
            ans.push_back(d.front());
        }

        return ans;
    }
};

Time Complexity: O(n)

Space Complexity: O(k)

Time Taken: 45m 28s