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

方铎码农普通 2024年3月29日上午12:13

//单调队列实现的滑动窗口
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 0 || k == 0) return new int[0];
        Deque<Integer> deque = new LinkedList<>();
        int[] res = new int[nums.length - k + 1];
        for(int j = 0, i = 1 - k; j < nums.length; i++, j++){
            if(i > 0 && deque.peekFirst() == nums[i - 1]){
                deque.removeFirst();
            }
            while(!deque.isEmpty() && deque.peekLast() < nums[j]){
                deque.removeLast();
            }
            deque.addLast(nums[j]);
            if(i >= 0){
                res[i] = deque.peekFirst();
            }
        }
        return res;
    }
}

用单调队列实现，队尾保持小队头保持大，队头始终是该滑动窗口的最大者

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

0 赞同 0 条回复

神经蛙普通 2024年3月27日上午12:34

class Solution {
public:
vector maxSlidingWindow(vector& nums, int k) {
if (nums.empty() || nums.size() < k) {
return vector();
}

    deque<int> queue;
    vector<int> res;

    for (int i = 0; i < nums.size(); i++) {
        while (!queue.empty() && nums[queue.back()] <= nums[i]) {
            queue.pop_back();
        }

        queue.push_back(i);

        if (queue.front() == i - k) {
            queue.pop_front();
        }

        if (i >= k - 1) {
            res.push_back(nums[queue.front()]);
        }
    }

    return res;
}

};
打卡

0 赞同 0 条回复

Jimmy 普通 2024年3月25日下午10:12

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

class Solution {
public:
    vector<int> maxAltitude(vector<int>& heights, int limit) {
        if(heights.empty() || heights.size()<limit)return vector<int> {};
        deque<int> que;
        vector<int> ans;
        for(int i=0;i<heights.size();i++)
        {
            while(!que.empty() && heights[que.back()] <= heights[i])//遇到更大的元素就把之前队列中的元素清空
            {
                que.pop_back();
            }
            que.push_back(i);

            if(que.front() == i-limit)//当队列最前面的元素==i-limit时，最前面的元素已经不属于滑动窗口范围之内了，所以需要将其剔除
            {
                que.pop_front();
            }
            if(i >= limit-1)
            {
                ans.push_back(heights[que.front()]);
            }
        }
        return ans;
    }
};

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年3月25日下午2:22

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums == null || nums.length <= 1){
            return nums;
        }
        //存放数组下标
        LinkedList<Integer> queue = new LinkedList<>();
        int[] res = new int[nums.length - k + 1];
        int index = 0; // res的下标

        for(int i = 0; i < nums.length; i++){
            //队伍前的数比当前数小，则不可能成为当前数组中的最大数，出队
            while(!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]){ 
                queue.pollLast();
            }

            queue.add(i);
//队满则从队头出队
            if(queue.peekLast() - k == queue.peek()){
                queue.poll();
            }

//从满足k个长度开始，队头就是数组最大值
            if(i + 1 >= k){
                res[index++] = nums[queue.peek()];
            }
        }

        return res;
    }
}

时间复杂度：O(n)
额外空间复杂的：O(k)

0 赞同 0 条回复

云无深雁影普通 2024年3月25日上午11:25

class Solution {
public int[] maxAltitude(int[] heights, int limit) {
if(heights.length 0)
return new int[0];
int[] ans = new int[heights.length – limit + 1];
List lower = new LinkedList<>();//一个非严格递减的队列

    for(int i = 0; i < limit; i++){ 
        while(!lower.isEmpty() && lower.getLast() < heights[i] )
            lower.removeLast();
        lower.addLast(heights[i]);
    }
    ans[0] = lower.getFirst();
    int begin = 0;
    int end = begin + limit - 1;
    while(end < heights.length -1){
        end++;
        if(lower.getFirst() == heights[begin])
            lower.removeFirst();

        while(!lower.isEmpty() && lower.getLast() < heights[end] )//每次新元素入队，就把队列中小于他的所有元素移除。保证队列的递减
            lower.removeLast();
        lower.addLast(heights[end]);           
        begin++;
        ans[begin] = lower.getFirst();
    }


    return ans;

}

}
//空间复杂度On
//时间复杂度Olimit

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月25日上午8:28

打卡

class Solution {
public:
    vector<int> maxAltitude(vector<int>& heights, int limit) {
        vector<int> res;
        deque<int> dq;
        // 滑窗一直保持头部为窗口最大值
        for(int i = 0; i < heights.size(); i++) {
           while(!dq.empty() && heights[dq.back()] < heights[i]) {
                dq.pop_back();
           }
            dq.push_back(i);
            if(i - limit == dq.front()) dq.pop_front();
            if(i >= limit - 1) res.push_back(heights[dq.front()]);
        }
        return res;
    }
};

0 赞同 0 条回复

南梁陈庆之普通 2024年3月25日上午12:57

暴力解决了，有空再看下滑动窗口吧~~~

class Solution {
    public int[] maxAltitude(int[] heights, int limit) {

         if(heights.length == 0 || limit == 0) return new int[0];
        // if (N == 0) {
        //     return new int[0]   ;
        // }
        int N = heights.length - limit + 1;
        int[] resArr = new int[N];
        Arrays.fill(resArr, Integer.MIN_VALUE);


        for (int i = 0; i < limit; i++) {
            resArr[0] = Math.max(resArr[0], heights[i]);
        }

        for (int i = limit , j = 1; i < heights.length; i++,j++) {
            for (int k = i; k > i - limit; k--) {
                resArr[j] = Math.max(resArr[j], heights[k]);
            }

        }
        return resArr;
    }
}

0 赞同 0 条回复

heathhou 普通 2024年3月24日下午11:28

class Solution {
public:
    vector<int> maxAltitude(vector<int>& heights, int limit) {
        if(heights.empty() || heights.size() < limit){
            return vector<int>();
        }

        deque<int> queue;
        vector<int> res;

        for(int i = 0; i < heights.size(); ++i){
            while(!queue.empty() && heights[queue.back()] <= heights[i]){
                queue.pop_back();
            }

            queue.push_back(i);

            if(queue.front() == i - limit){
                queue.pop_front();
            }

            if(i + 1 >= limit){
                res.push_back(heights[queue.front()]);
            }
        }

        return res;
    }
};

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

0 赞同 0 条回复

机电皮怪永久会员 2024年3月24日下午11:23

本来用的是暴力法，然后看了视频之后用了时间复杂度O(n)，空间复杂度O(n)的方法

“`C++
class Solution {
public:
vector maxAltitude(vector& heights, int limit) {
if(heights.empty() == true || heights.size() < limit) { return heights; } int length = heights.size(); vector res;
deque queue;
//用队列记录最大值的序号，队列头部是最大值
for(int i = 0; i < length; i++) { //窗口有更大值则弹出尾部小值 while(queue.empty() == false && heights[queue.back()] <= heights[i]) { queue.pop_back(); }

       queue.push_back(i);

        //出了窗口左边界
       if(queue.front() == i - limit)
       {
            queue.pop_front();
       }

        //长度达到窗口长度后每次移动要加入一个最大值
       if(i >= limit - 1)
       {
            res.push_back(heights[queue.front()]);
       }
    }
    return res;
}

};

“`

0 赞同 0 条回复

紫芝普通 2024年3月24日下午10:52

思路：单调队列

func maxAltitude(heights []int, limit int) []int {
    var ans []int
    if len(heights) == 0 { return ans }
    queue := list.New()
    for i:=0; i<limit; i++ {
        for queue.Len() != 0 && (heights[i] > queue.Back().Value.(int)) { queue.Remove(queue.Back()) }
        queue.PushBack(heights[i])
    }

    ans = append(ans, queue.Front().Value.(int))
    for i:=limit; i<len(heights); i++ {
        if heights[i-limit] == queue.Front().Value.(int) {
            queue.Remove(queue.Front())
        }
        for queue.Len() != 0 && heights[i] > queue.Back().Value.(int) { queue.Remove(queue.Back()) }
        queue.PushBack(heights[i])
        ans = append(ans, queue.Front().Value.(int))
    }

0 赞同 0 条回复

Raphtalia. 普通 2024年3月24日下午10:09

class Solution {
public:
vector maxAltitude(vector& heights, int limit) {
vector res;
if(heights.size() < limit || heights.size() 0) return res;
deque q; //单调队列,存储标号
for(int i = 0; i < heights.size() ; i ++) {
//维护单调递减
while(!q.empty() && heights[i] > heights[q.back()]) q.pop_back();
q.push_back(i);
if(i – q.front() >= limit) q.pop_front();
//output
if(i + 1 >= limit) {
res.push_back(heights[q.front()]);
}
}
return res;
}
};
时间复杂度O(N)，空间复杂度O（limit）

0 赞同 0 条回复

言之命至普通 2024年3月24日下午9:38

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums == null || nums.length <= 1){ //判断特殊情况
            return nums;
        }

        LinkedList<Integer> queue = new LinkedList<>();//定义队列
        int[] res = new int[nums.length - k + 1];
        int index = 0;

        //K

        for(int i = 0; i < nums.length; i++){
            while(!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]){//如果队列非空，并且队头元素小于改元素，出队
                queue.pollLast();
            }

            queue.add(i);

            if(queue.peekLast() - k == queue.peek()){
                queue.poll();//如果最下面的元素不在滑动窗口的范围内，出队
            }

            if(i + 1 >= k){
                res[index++] = nums[queue.peek()];
            }
        }

        return res;
    }
}

时间O（n），空间：O（1）

0 赞同 0 条回复

王位詮釋普通 2024年3月24日下午8:34

class Solution {
    public int[] maxAltitude(int[] heights, int limit) {
        if(heights.length==0){
            return heights;
        }
        int l = 0;
        int r = limit-1;
        int[] ret = new int[heights.length-limit+1];
        for(;rmax?nums[i]:max;
        }
        return max;
    }
}
思路：固定滑动窗口的大小，每次只往后移动一格，并且随着移动获取滑动窗口内的最大值，这个题比较烦的是最后返回结果如果直接用list.toArray()的话，返回的是一个引用对象，不能直接返回，这点我开始时候不知道有没有别的接口可以简化，所以就自己遍历了一遍数组再返回。之后发现返回数组长度是可以确定的，所以直接创建ret数组而不是用list来存储最大值。
时间复杂度：因为滑动窗口每次只需要往后一个，时间复杂度应该是O(limit(n-limit))=O(n*limit)，空间复杂度O(1)

0 赞同 0 条回复

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

共以下 13 个回答

# 回答此问题取消回复

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

共以下 13 个回答

# 回答此问题 取消回复

# 回答此问题取消回复