【滑动窗口专题】剑指 Offer 59 – I. 滑动窗口的最大值-跟着帅地玩副业，开拓第二曲线PlayOffer

lQl 永久会员 2024年12月22日下午6:43

将可能作为最大值的放入队列中,按顺序取出即可,为保证单调性,每次移动时小的数放在后面,大的数直接把之前清空再添加

class Solution {
    public int[] maxAltitude(int[] heights, int limit) {
        if (heights.length == 0 || limit == 0)
            return new int[0];
        Deque<Integer> deque = new LinkedList<>();
        int[] result = new int[heights.length - limit + 1];
        for (int i = 0; i < limit; i++) {
            while (!deque.isEmpty() && deque.peekLast() < heights[i])
                deque.removeLast();
            deque.addLast(heights[i]);
        }
        result[0] = deque.peekFirst();
        for (int i = limit; i < heights.length; i++) {
            if (deque.peekFirst() == heights[i - limit])
                deque.removeFirst();
            while (!deque.isEmpty() && deque.peekLast() < heights[i])
                deque.removeLast();
            deque.addLast(heights[i]);
            result[i - limit + 1] = deque.peekFirst();
        }
        return result;
    }
}

时间复杂度O(n)
空间复杂度O(limit)

0 赞同 0 条回复

陆狗陆狗普通 2024年12月18日上午1:26

解题思路
– 使用单调队列来存储（条件范围内的最大值的顺序）
– 队列头->尾巴：从大->小（越老的越在前面），新元素都是offerLast
– 每一次右边界右移都需要考虑：
– 1、新节点比队列里面哪些元素要大，就淘汰那些元素（从尾巴去淘汰）
– 2、哪些节点已经比左边界小了，就淘汰那些元素（从头去淘汰）
– 左边界右移只需要从队列里面取最大值即可，不需要考虑淘汰元素的问题
【题解1】

class Solution {
    public int[] maxAltitude(int[] heights, int limit) {
        // 【错误点】边界情况
        if (heights == null || heights.length == 0) {
            return heights;
        }
        // 需要用1个队列来存储从左到右的最大值的下标()
        Deque<Integer> q = new LinkedList<Integer>();
        int left = 0;
        int right = 0;
        // 结果
        int[] res = new int[heights.length - limit + 1];
        int i = 0;
        // 右滑的临界点
        while (right <= heights.length - 1) {
            if (right - left < limit) {
                // 队列头->尾巴：从大->小 （越老的越在前面）
                // 1、新节点比队列里面哪些元素要大，就淘汰那些元素（从尾巴去淘汰）
                // 2、哪些节点已经比左边界小了，就淘汰那些元素（从头去淘汰）
                // 【错误点】队列是否为空，用q.isEmpty()就可以判断
                // 【错误点】使用Deque队列就能在左边和右边同时添加数据了
                while (!q.isEmpty() && heights[q.peekLast()] < heights[right]) {
                    q.pollLast();
                }
                while (!q.isEmpty() && q.peekFirst() < left) {
                    q.pollFirst();
                }
                // 淘汰完毕之后，就把新元素的下标放到队列队尾
                q.offerLast(right);
                // 右边右滑
                right++;
            }
            // 【错误点】右边移动之后++ 可能就满足right - left == limit了，就可以求最大值l
            if (right - left == limit) {
                // 取出最大值
                res[i++] = heights[q.peek()];
                // 左边左滑
                left++;
            }
        }

        // 返回结果
        return res;

    }
}

错误点1：数组的边界情况未考虑
错误点2：队列是否为空，用q.isEmpty()就可以判断
错误点3：使用Deque队列就能在左边和右边同时添加数据了

0 赞同 0 条回复

Jerry 普通 2024年12月17日下午9:13

class Solution {
public:
    vector<int> maxAltitude(vector<int>& heights, int limit) {
        if(heights.size() == 0) return {};
        vector<int> res;
        deque<int> dq;

        for(int i = 0; i < heights.size(); i++){
            while(!dq.empty() && dq.back() < heights[i]){
                dq.pop_back();
            }
            dq.push_back(heights[i]);
            int start = i - limit;
            if(start == -1){
                res.push_back(dq.front());
                continue;
            }
            if(start < 0){
                continue;
            }
            if(heights[start] == dq.front()){
                dq.pop_front();
            }
            res.push_back(dq.front());
        }
        return res;
    }
};

利用双端队列实现
单调队列的功能

0 赞同 0 条回复

秋山丽奈普通 2024年12月17日下午7:49

思路：使用栈实现

class Solution {
    public int[] maxAltitude(int[] heights, int limit) {
        int len = heights.length;

        int[] ans = new int[len-limit+1];

        Stack<Integer> maxStack = new Stack<>();

        maxStack.push(heights[0]);
        int currentMax = Integer.MIN_VALUE;

        // 第一组 入栈 
        for(int i = 1; i < limit; i ++){
            List<Integer> temp = new ArrayList<>();
            int current = maxStack.peek();
            while(!maxStack.isEmpty() && current > heights[i]){
                temp.add(maxStack.pop());
            }

            maxStack.push(heights[i]);
            for(int push: temp){
                maxStack.push(push);
            }
        }

        int tail = limit;
        while(tail < len){
            ans[tail-limit] = maxStack.peek();

            // 左端首先 向前 
            List<Integer> temp = new ArrayList<>();
            int current = maxStack.peek();
            while(!maxStack.isEmpty() && current != heights[tail]){
                temp.add(maxStack.pop());
            }

            if(!maxStack.isEmpty()){
                maxStack.pop();
            }
            for(int push: temp){
                maxStack.push(push);
            }

            // 右端首先 向前
            temp = new ArrayList<>();
            current = maxStack.peek();
            while(!maxStack.isEmpty() && current > heights[tail]){
                temp.add(maxStack.pop());
            }

            maxStack.push(heights[tail]);
            for(int push: temp){
                maxStack.push(push);
            } 

            tail ++;
        }

        ans[tail-limit] = maxStack.peek();

        return ans;

    }
}

0 赞同 0 条回复

迢迢星野普通 2024年12月16日下午7:13

class Solution {

    // 单调队列实现滑动窗口中的最大值
    class Window {
        LinkedList<Integer> que = new LinkedList<>();

        public void push(int val) {
            while(!que.isEmpty() && que.peekLast() < val) {
                que.removeLast();
            }
            que.addLast(val);
        }

        public void pop(int val) {
            if(val == que.peekFirst()) {
                que.removeFirst();
            }
        }

        public int max() {
            return que.peekFirst();
        }
    }

    public int[] maxAltitude(int[] heights, int limit) {
        int n = heights.length;
        if(n == 0) {
            return heights;
        }
        Window window = new Window();
        int[] ans = new int[n - limit + 1];
        int idx = 0;
        for(int i = 0; i < n; i++) {
            if(i < limit - 1) {
                window.push(heights[i]);
            }else {
                window.push(heights[i]);
                ans[idx++] = window.max();
                window.pop(heights[i - limit + 1]);
            }
        }
        return ans;
    }
}

思路：维护一个单调队列，保证队列中存储的是滑动窗口内的最大值
时间复杂度：O(n)
空间复杂度：O(n)

0 赞同 0 条回复

Xiang. 永久会员 2024年12月16日下午7:05

class Solution {
    //思路：借用队列，该队列满足：
    //①入队元素对应的海拔高度要尽可能的大，即如果新入队的元素大于它之前的元素，则要将小的元素出队
    //②队中元素不能超过limit个
    public int[] maxAltitude(int[] heights, int limit) {
        if(heights.length<=1) return heights;
        LinkedList<Integer> queue=new LinkedList<>();
        int[] res=new int[heights.length-limit+1];
        int num=0;      //记录res最新存入元素的位置
        for(int i=0;i<heights.length;i++){
            //当queue不为空时，保证队中现存的元素均要大于要入队的元素。
            while(!queue.isEmpty()&&heights[queue.peekLast()]<=heights[i]){
                queue.pollLast();
            } 
            queue.add(i);
            if(queue.peekLast()-queue.peek()==limit) queue.poll(); //队中元素不能超过limit个
            if(i+1>=limit) res[num++]=heights[queue.peek()]; 
        }
        return res;

    }
}
时间复杂度：O（n）
空间复杂度：O（m）//对应queue的大小

0 赞同 0 条回复

Aatorx 永久会员 2024年12月16日下午3:21

class Solution {
public:
    vector<int> maxAltitude(vector<int>& heights, int limit) {
        vector<int> res;
        if (heights.empty()) {
            return res;
        }
        priority_queue<pair<int, int>> q;
        for(int i = 0; i < limit; i++) {
            q.emplace(heights[i], i);
        }
        res.push_back(q.top().first);
        for (int i = limit; i < heights.size(); i++) {
            q.emplace(heights[i], i);
            while (q.top().second <= i - limit) {
                q.pop();
            }
            res.push_back(q.top().first);
        }
        return res;
    }
};

利用大根堆来记录滑动窗口最大值以及下标，当下标超出范围时删除堆顶的元素。
时间复杂度O(Nlogn)，空间复杂度O(N)。

0 赞同 0 条回复

月下足迹普通 2024年12月15日上午11:25

public int[] maxAltitude(int[] heights, int limit) {
if (heights.length 0) {
int[] result = new int[0];
return result;
}
int n = heights.length;
int[] result = new int[n – limit + 1];
Deque deque = new ArrayDeque<>(); // 双端队列存储索引

    for (int i = 0; i < n; i++) {
        // 移除窗口外的索引
        if (!deque.isEmpty() && deque.getFirst() < i - limit + 1) {
            deque.pollFirst();
        }
        // 移除所有小于当前值的索引（保持队列单调递减）
        while (!deque.isEmpty() && heights[deque.getLast()] <= heights[i]) {
            deque.pollLast();
        }
        // 将当前索引加入队列
        deque.addLast(i);

        // 当窗口形成时（即 i >= limit - 1），记录窗口最大值
        if (i >= limit - 1) {
            result[i - limit + 1] = heights[deque.getFirst()];
        }
    }
    return result;
}

0 赞同 0 条回复

Kisara 普通 2024年12月14日下午3:49

思路

通过一个双端队列，维护一个递减的队列
分两步走，一步是还没形成3个值的窗口时，还有是已经形成时
只要值比队尾小，就入队，若值比队尾大，则队列里的所有值都不可能在以后成为最大，所以全部删去
在每次循环判断一下队头是不是已经超出窗口范围了，若超出就出队
需要输出最大值的时候只需要输出队头

代码

class Solution {
    public int[] maxAltitude(int[] heights, int limit) {
        if(heights==null||heights.length==0||limit<1) return new int[0];

        ArrayDeque deque = new ArrayDeque<>();
        List result =new ArrayList<>();

        for(int i=0;iheights[deque.peekLast()]){
                deque.pollLast();
            }
            deque.offerLast(i);
        }
        result.add(heights[deque.peekFirst()]);

        for(int i=limit;iheights[deque.peekLast()]){
                deque.pollLast();
            }
            deque.offerLast(i);
            result.add(heights[deque.peekFirst()]);

        }
        return result.stream().mapToInt(i->i).toArray();

    }
}

OnOn

0 赞同 0 条回复

苯庸普通 2024年12月14日下午12:13

class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] res = new int[n – k + 1];
int j = 0;
Deque deque = new ArrayDeque();
for(int i = 0;i < n; i++){
while(!deque.isEmpty() && i – deque.peek() + 1 > k){
deque.poll();
}
while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]){
deque.pollLast();
}
deque.offer(i);
if(i >= k-1){
res[j++] = nums[deque.peek()];
}
}
return res;
}
}
时间：O（n）
空间：O（n）

0 赞同 0 条回复

晓宇普通 2024年12月14日下午12:10

// 挨个滑动窗口搜索最大值
class Solution {
public:
    vector<int> maxAltitude(vector<int>& heights, int limit) {
        if(limit <= 0 || heights.empty()) return vector<int> ();
        else if(heights.size() <= limit) 
            return vector<int> {*max_element(heights.begin(),heights.end())};
        vector<int> ans;

        for(int i = 0;i <= heights.size() - limit;i ++){
            auto max_it = max_element(heights.begin() + i,heights.begin() + i + limit); // [)
            ans.push_back(*max_it);

        }
        return ans;
    }
    // o(n) o(n)
};

// 滑动窗口 维护一个优先队列
class Solution {
public:
    vector<int> maxAltitude(vector<int>& heights, int limit) {
        if(heights.size() <= 1) return heights;
        vector<int> ans;
        deque<int> q;  // 队列首端为窗口最大值

        for(int i = 0;i < heights.size(); i++){
            while(!q.empty() && heights[q.back()] <= heights[i]) // 新元素如果大于队尾元素，则弹出队尾
                q.pop_back();
            q.push_back(i);  // 存入新元素序号
            if(q.front() == i - limit)  // 队首在窗口外，则弹出
                q.pop_front();

            if(i >= limit -1)  
                ans.push_back(heights[q.front()]);

        }
        return ans;
    }
};
// o(n) o(n)

0 赞同 0 条回复

jaron 普通 2024年12月14日上午9:28

class Solution {
    public int[] maxAltitude(int[] nums, int k) {
        if (nums == null || nums.length <= 1) {
            return nums;
        }
        // 双端队列里存放下标
        LinkedList<Integer> queue = new LinkedList<>();
        int[] ans = new int[nums.length - k + 1];
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            // 把队尾所有小的数反向出队
            while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]) {
                queue.pollLast();
            }
            queue.add(i);
            // 把队首不在窗口里的下标出队
            if (queue.peekLast() - queue.peek() == k) {
                queue.poll();
            }
            if (i + 1 >= k) {
                ans[index++] = nums[queue.peek()];
            }
        }
        return ans;
    }
}

0 赞同 0 条回复

【滑动窗口专题】剑指 Offer 59 – I. 滑动窗口的最大值

共以下 12 个回答

思路

代码

# 回答此问题取消回复

【滑动窗口专题】剑指 Offer 59 – I. 滑动窗口的最大值

共以下 12 个回答

思路

代码

# 回答此问题 取消回复

# 回答此问题取消回复