面试题59 - I：滑动窗口的最大值（C++）

class Solution {
public:
    vectorint> maxSlidingWindow(vectorint>& nums, int k) {
        if(nums.size() == 0) return nums; //nums.empty()
        int len = nums.size() - k + 1; //输出数组长度大小
        vectorint> arr;
        
        for(int i = 0; i )
        {
            int max_num = nums[i];
            for(int j = i + 1; j )
            {
                max_num = max(nums[j], max_num);
            }
                arr.push_back(max_num);
        }
        return arr;
    }
};

class Solution {
public:
    vectorint> maxSlidingWindow(vectorint>& nums, int k) {
        if(nums.size() == 0) return nums;
        vectorint> dp(nums.size() - k + 1, INT_MIN);
        for(int i = 0; i )
        {
            dp[0] = max(dp[0], nums[i]);
        }
        for(int i = 1; i )
        {
            if(nums[i - 1] 1])
            {
                dp[i] = max(dp[i - 1], nums[i + k - 1]); //转入下一个滑动窗口，即比较dp[0]和nums[3]
            }
            else //比如dp[1]=3与nums[1]=3
            {
                for(int j = i; j )
                {
                    dp[i] = max(dp[i], nums[j]); //比如滑动窗口[-1,-3,5]与dp[2]
                }
            }
        }
        return dp;
    }
};

class Solution {
public:
    vectorint> maxSlidingWindow(vectorint>& nums, int k) {
        if(nums.size() == 0) return nums;
        vectorint> arr;
        dequeint> dq;
        for(int i = 0; i )
        {
            while(!dq.empty() && nums[i] > nums[dq.back()]) dq.pop_back();
            if(!dq.empty() && dq.front()  k)) dq.pop_front();
            dq.push_back(i);
            if(i >= k - 1) arr.push_back(nums[dq.front()]);
        }
        return arr;
      /*  vector arr;
        deque dq; //保存有可能成为滑动窗口最大值的数字的下标
        for(int i = 0; i */
    }
};