题解 | #滑动窗口的最大值#

滑动窗口的最大值

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

  • 暴力:

    vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
    if (num.size() < size || size == 0) return { };
    vector<int> ans;
    for (int i = 0; i <= num.size() - size; ++i) {
      ans.emplace_back(*max_element(num.begin() + i, num.begin() + i + size));
    }
    return ans;
    }
  • 单调队列:

    class MyQueue {
    public:
    void push(int val) {
      while (!que_.empty() && que_.back() < val) {
        que_.pop_back();
      }
      que_.emplace_back(val);
    }
    
    void pop(int val) {
      if (que_.front() == val) {
        que_.pop_front();
      }
    }
    
    int max() {
      return que_.front();
    }
    

private:
deque<int> que_;
};</int>

vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
if (num.size() < size || size == 0) return { };
vector<int> ans;
MyQueue que;
for (int i = 0; i < num.size(); ++i) {
if (i < size - 1) {
que.push(num[i]);
} else {
que.push(num[i]);
ans.emplace_back(que.max());
que.pop(num[i - size + 1]);
}
}
return ans;
}</int></int></int>

```

全部评论

相关推荐

身边有人上海、深圳&nbsp;6、7k&nbsp;都去了,真就带薪上班了。
程序员小白条:木的办法, 以后越来越差,还是家附近宅着吧,毕业的人越来越多,岗位都提供不出来,经济又过了人口红利期
点赞 评论 收藏
分享
nus2201602...:兄弟,你这个简历撕了丢了吧,就是一坨,去找几个项目,理解项目流程,看几遍就是你的了,看看八股就去干了,多看看牛客里别人发出来的简历,对着写,你这写的啥啊,纯一坨
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-04 18:25
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务