【重点】【单调队列】剑指offer——面试题65：滑动窗口的最大值

Allenlzcoder

已于 2025-05-15 01:10:55 修改

阅读量262

点赞数

分类专栏：剑指offer题目笔记文章标签：剑指offer 滑动窗口的最大值

于 2018-04-05 17:16:13 首次发布

本文链接：https://blog.csdn.net/Allenlzcoder/article/details/79827682

版权

剑指offer题目笔记专栏收录该内容

80 篇文章

订阅专栏

本文介绍了两种求解滑动窗口最大值问题的方法：暴力遍历和使用双端队列。暴力方法通过逐个检查每个窗口的最大值实现，而双端队列方法则通过维护一个递减序列来高效获取最大值。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

力扣，https://leetcode.cn/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/description/

最佳方案：单调队列

class Solution:
    def maxAltitude(self, heights: List[int], limit: int) -> List[int]:
        res = []
        queue = collections.deque() # 单调递减队列
        for i, x in enumerate(heights):
            if len(queue) == 0:
                queue.append(i)
            else:
                while len(queue) > 0 and heights[queue[-1]] <= x:
                    queue.pop()
                queue.append(i)
                if i - queue[0] >= limit:
                    queue.popleft()
            if i+1 >= limit:
                res.append(heights[queue[0]])
        return res

解法1：暴力遍历

class Solution {
    public int[] maxAltitude(int[] heights, int limit) {
        if (heights.length == 0) {
            return new int[0];
        }
        int[] res = new int[heights.length - limit + 1];
        int val = Integer.MIN_VALUE;
        for (int i = 0; i + limit <= heights.length; ++i) {
            val = Integer.MIN_VALUE;
            for (int k = i; k < i + limit; ++k) {
                val = val > heights[k] ? val : heights[k];
            }
            res[i] = val;
        }

        return res;
    }
}

解法2：双端队列

关于java中LinkedList，Stack，Queue，Deque总结

class Solution {
    public int[] maxAltitude(int[] heights, int limit) {
        if (heights.length == 0) {
            return new int[0];
        }
        Deque<Integer> deque = new LinkedList<>();
        int[] res = new int[heights.length - limit + 1];
        for (int i = 0; i < limit; ++i) {
            if (deque.size() == 0) {
                deque.offerLast(heights[i]);
            } else {
                while (deque.size() > 0 && deque.peekLast() < heights[i]) {
                    deque.pollLast();
                }
                deque.offerLast(heights[i]);
            }
        }
        res[0] = deque.peekFirst();
        for (int right = limit; right < heights.length; ++right) {
            int left = right - limit;
            if (heights[left] == deque.peekFirst()) {
                deque.pollFirst();
            }
            while (deque.size() > 0 && deque.peekLast() < heights[right]) {
                deque.pollLast();
            }
            deque.offerLast(heights[right]);
            res[right - limit + 1] = deque.peekFirst();
        }

        return res;
    }
}

##Solution1:
笨蛋方法啊。。

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
        vector<int> res;
        if(num.size() == 0 || size <= 0 || num.size() < size)
            return res;
        int start = 0, end = size - 1;
        int max_win = my_max(num, start, end);
        res.push_back(max_win);
        start++;
        end++;
        while(end < num.size()) {
            max_win = my_max(num, start, end);
            res.push_back(max_win);
            start++;
            end++;
        }
        return res;
    }
    
    int my_max(const vector<int>& num, int start, int end) {
        int res = INT_MIN;
        for(int i = start; i <= end; i++) {
            if(num[i] >= res)
                res = num[i];
        }
        return res;
    }
};

#Solution2:
20180916日重做
参考网址：https://www.nowcoder.com/profile/1710251/codeBookDetail?submissionId=17436906
这个思路真是精巧~

//引用马客（Mark）的解题思路，马客没加注释，我用自己的理解加下注释，希望对你们有用，
//如有错误，见谅，我会及时修改。
//deque s中存储的是num的下标
class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
        vector<int> res;
        deque<int> s;
        for(unsigned int i=0;i<num.size();++i){
            while (s.size() && num[s.back()] <= num[i])
            //从后面依次弹出队列中比当前num值小的元素，同时也能保证队列首元素为当前窗口最大值下标
                s.pop_back();
            while (s.size() && i - s.front() + 1>size)
            //当当前窗口移出队首元素所在的位置，即队首元素坐标对应的num不在窗口中，需要弹出
                s.pop_front();
            s.push_back(i);//把每次滑动的num下标加入队列
            if (size && i >= size - 1)
            //当滑动窗口首地址i大于等于size时才开始写入窗口最大值
                res.push_back(num[s.front()]);
        }
        return res;
    }
};