Accepted 104ms c++ solution with MaxQueue.


  • 11

    Do you remember the Min Stack problem? In this problem, a similar Max Queue is needed!

    Here is my 104ms c++ solution.

    class Solution {
    public:
    	std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) {
    		std::vector<int> res;
    		if (k < 1)
    			return res;
    		MaxQueue mq;
    		for (int i = 0; i != k; ++i)
    			mq.push(nums[i]);
    		res.push_back(mq.getMax());
    		for (int i = k; i != nums.size(); ++i) {
    			mq.pop();
    			mq.push(nums[i]);
    			res.push_back(mq.getMax());
    		}
    		return res;
    	}
    private:
    	class MaxQueue {
    	public:
    		void push(int x) {
    			nums.push(x);
    			while (!maxs.empty() && maxs.back() < x)
    				maxs.pop_back();
    			maxs.push_back(x);
    		}
    		void pop() {
    			if (nums.front() == maxs.front())
    				maxs.pop_front();
    			nums.pop();
    		}
    		int getMax() {
    			return maxs.front();
    		}
    	private:
    		std::queue<int> nums;
    		std::deque<int> maxs;
    	};
    };
    

  • 0
    L

    I assume it is better not to use "std::queue<int> nums;" for MaxQueue. Since it will take O(k) extra space which is unnecessary. You use it only for pop() function to avoid maxs.pop_front() when it is a deleted element of the queue.This could be done by just comparing the left most element of the window with the MAX of queue: if < do nothing otherwise pop the queue. Then you don't need the counter now. :)

     void pop(int leftMostOfWindow) {
                if (leftMostOfWindow == maxs.front())
                    maxs.pop_front();
            }
    

    Here is my solution using Arraylist.

    public class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            if(nums.length==0) return new int[0];
            List<Integer> descList = new ArrayList<Integer>();
            int[] res = new int[nums.length+1-k];
            for(int i=0;i<k-1;i++) addDescList(descList,nums[i]);
            for(int i=0;i<res.length;i++){
                addDescList(descList,nums[i+k-1]);
                res[i] = descList.get(0);
                if(nums[i]==descList.get(0)) descList.remove(0); //to delete the left most.
            }
            return res;   
        }
        public void addDescList(List<Integer> descList, int num){
            while(!descList.isEmpty()&&num>descList.get(descList.size()-1)) descList.remove(descList.size()-1);
            descList.add(num);
        }  
    }

  • 0
    G

    How can this be O(n)? This is O(kn) since the push needs k.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.