优于网上博客:LeetCode 239. Sliding Window Maximum 没那么反人类的C++代码


这题尝试做了下,思路错误WA,看博客,C++代码实在是不敢恭维,重写之后发上来。。
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> result;
        int size = nums.size();
        if(size <= 0 || k <= 0){
            return result;
        }
        
        deque<int> deque;
        for(int i = 0;i < k;++i){
            while(!deque.empty() && nums[i] >= nums[deque.back()]){
                deque.pop_back();
            }
            deque.push_back(i);
        }
        
        result.push_back(nums[deque.front()]);
        for(int i = k;i < size;++i){
            while(!deque.empty() && i - deque.front() >= k){
                deque.pop_front();
            }            

            while(!deque.empty() && nums[i] >= nums[deque.back()]){
                deque.pop_back();
            }

            deque.push_back(i);
            result.push_back(nums[deque.front()]);
        }
        return result;
    }
};
已邀请:

要回复问题请先登录注册

返回顶部