C++deque的用法

滑动窗口的最大值

http://www.nowcoder.com/practice/1624bc35a45c42c0bc17d17fa0cba788

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
        vector<int> v;
        deque<int> dq;
        if(size > num.size() || !size) return v;
        for(int i = 0; i < num.size(); ++i) {
            while(!dq.empty() && num[dq.back()] < num[i]) dq.pop_back();
            dq.push_back(i);
            if(dq.front() + size <= i) dq.pop_front();
            if(i + 1 >= size)
                v.push_back(num[dq.front()]);
        }
        return v;
    }
};
全部评论

相关推荐

点赞 评论 收藏
分享
2 1 评论
分享
牛客网
牛客企业服务