欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

239.滑动窗口的最大值

程序员文章站 2024-03-19 22:19:10
...

 正确的解法是使用双端队列来处理这个window的功能。

c++ deque有现成的stl可以使用

需要注意几个点

1. 需要维护队列内部的最大值在队首的位置,每次想要添加一个新元素的时候就循环和前面的元素做比较

2. 判断一个元素是否过期,可以直接用当前队首和应该淘汰的数字进行对比如果一致就去除

主要逻辑:

1. 如果该数据小于新加入的数据,再上一步就应该被清除所以不需要考虑过期的问题

2. 如果当前的数据大于新加入的数据,但是又恰好等于i -k这个位置的数据,那么在确定最大值之前就需要将它清理出来

/*
 * @lc app=leetcode.cn id=239 lang=cpp
 *
 * [239] 滑动窗口最大值
 * 使用deque双端队列的方法来解决,效率比较低
 */

// @lc code=start
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if(nums.size() < 1) return vector<int>();
        if(k == 1) return nums;
        if(nums.size() <= k) return vector<int>{ *std::max_element(nums.begin(),nums.end())};
        vector<int> ret;
        deque<int> window;
        window.push_front(nums[0]);

        for (int i = 1; i < nums.size() ; i++) {
            //这里面有一个循环剔除前面所有的数据
            while (window.size() > 0 && nums[i] > window.back()) {
                window.pop_back();
            }
            window.push_back(nums[i]);
            //window front用来判断是否是过期的数据,如果有重复数据也应该被前面循环所去除
            if (i >= k && window.front() == nums[i - k]) {
                window.pop_front();    
            } 
            if (i >= k - 1) {
                ret.push_back(window.front());
            }
        }         
        return ret;
    }
};
// @lc code=end

deque的性能确实不怎么的,如果可以还是用数据效率比较高,但是容器就是胜在了方便

 

相关标签: