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

桎梏普通 2023年9月13日下午10:07

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {

        if (nums.length == 1) return nums;

        int[] res = new int[nums.length - k + 1];
        int num = 0;

        MyQueue myQueue = new MyQueue();

        for(int i=0; i<k; i++) {
            myQueue.add(nums[i]);
        }

        res[num++] = myQueue.peek();

        for(int i=k; i<nums.length; i++) {
            myQueue.poll(nums[i - k]);
            myQueue.add(nums[i]);
            res[num++] = myQueue.peek();
        }
        return res;
    }
}

class MyQueue {

    Deque<Integer> deque = new LinkedList<>();

    void poll(int val) {
        //当需要弹出的元素等于队头元素时 才执行弹出操作 即保存窗口中的最大值
        if (!deque.isEmpty() && val == deque.peek()) {
            deque.poll();
        }
    }

    void add(int val) {
        //需要保证队列元素单调递减
        while(!deque.isEmpty() && val > deque.getLast()) {
            deque.removeLast();
        }
        deque.add(val);
    }

    int peek() {
        //队头元素始终为最大值
        return deque.peek();
    }
}

0 赞同 0 条回复

June 普通 2023年9月10日下午3:47

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] ans = new int[nums.length - (k-1)];
        Deque<Integer> dq = new LinkedList<Integer>();
        for(int i=0;i<k;i++)
        {
            while(!dq.isEmpty() && nums[i] >= nums[dq.peekLast()] )
                dq.pollLast();
            dq.offerLast(i);
        }
        ans[0] = nums[dq.peekFirst()];
        for(int i=k;i<nums.length;i++)
        {
             while(!dq.isEmpty() && nums[i] >= nums[dq.peekLast()] )
                dq.pollLast();
            dq.offerLast(i);
            while (dq.peekFirst() <= i-k ) // 最左边那个已经不在滑动窗口内了
                dq.pollFirst();
            ans[i - k + 1] = nums[dq.peekFirst()];
        }
        return ans;
    }
}

0 赞同 0 条回复

hi 普通 2023年9月3日下午8:28

队头超过窗口左边界，对头出队
如果遇到更大的值，队尾出队，加入这个更大的元素

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        int n = nums.size();
        int q[n];
        int hh = 0, tt = -1;
        for(int i = 0; i < n; i++)
        {
            if(hh <= tt && i - k + 1 > q[hh]) hh ++;
            while(hh <= tt && nums[q[tt]] < nums[i]) tt--;
            q[++tt] = i;
            if(i >= k - 1) res.push_back(nums[q[hh]]);
        }
        return res;
    }
};

0 赞同 0 条回复

普通 2023年8月10日下午10:46

c++ 代码单调队列
class Solution {
public:
vector maxSlidingWindow(vector& nums, int k)
{
vector cc;
deque maxx;
for(int i=0;i<nums.size();i++)
{
while(!maxx.empty()&&nums[maxx.back()]<=nums[i])
maxx.pop_back();
maxx.push_back(i);
if(i-kmaxx.front())
maxx.pop_front();
if(i>=k-1)
cc.push_back(nums[maxx.front()]);
}
return cc;
}
};

0 赞同 0 条回复

北辰普通 2023年8月8日上午9:57

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>(){
            public int compare(int[] pair1,int[] pair2) {
                return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
            }
        });
        for(int i=0;i<k;i++) {
            pq.offer(new int[] {nums[i],i});
        }
        int[] ans = new int[n-k+1];
        ans[0] = pq.peek()[0];
        for(int i=k;i<n;++i) {
            pq.offer(new int[] {nums[i],i});
            while(pq.peek()[1]<=i-k) {
                pq.poll();
            }
            ans[i-k+1]=pq.peek()[0];
        }
        return ans;
    }
}

时间复杂度：O（nlogn)
空间复杂度：O（n)

0 赞同 0 条回复

CKX 普通 2023年8月7日上午12:03

type MonotonicQueue struct {
    q []int
}

func (mq *MonotonicQueue) push(n int) {
    // 将小于 n 的元素全部删除
    for len(mq.q) > 0 && mq.q[len(mq.q)-1] < n {
        mq.q = mq.q[:len(mq.q)-1]
    }
    // 然后将 n 加入尾部
    mq.q = append(mq.q, n)
}

func (mq *MonotonicQueue) max() int {
    return mq.q[0]
}

func (mq *MonotonicQueue) pop(n int) {
    if n == mq.q[0] {
        mq.q = mq.q[1:]
    }
}

func maxSlidingWindow(nums []int, k int) []int {
    window := &MonotonicQueue{}
    res := make([]int, 0)
    for i := 0; i < len(nums); i++ {
        if i < k-1 {
            //先填满窗口的前k-1
            window.push(nums[i])
        } else {
            // 窗口向前滑动，加入新数字
            window.push(nums[i])
            // 记录当前窗口的最大值
            res = append(res, window.max())
            // 移出旧数字
            window.pop(nums[i-k+1])
        }
    }
    return res
}

时间O(n)
空间O(n)

0 赞同 0 条回复

#00456B 普通 2023年8月4日上午12:14

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        //单调队列,front到back递减
        vector<int> ans;
        deque<int> que;//que存放的是数值，不是下标
        //先载入前k个，符合条件的push到que
        for(int i = 0; i < k;i++){
            while(!que.empty() && nums[i] > que.back()){
                //不能写作>=，否则只会保留前一个最大值，在超过k个之后会被抹除
                //例如 [-7,-8,7,5,7,1,6,0]  4
                //在7,5,7,1中如果用>=，que只会保留第一个7，在滑动窗口到达6时这个7会被剔除，但是此时最大值应仍为7
                que.pop_back();
            }
            que.push_back(nums[i]);
        }
        ans.push_back(que.front());
        for(int i = k; i < nums.size(); i++){
            //pop掉第i-k个元素
            if(!que.empty() && que.front() == nums[i-k]){
                que.pop_front();
            }
            //push进第i个元素
            while(!que.empty() && nums[i] > que.back()){
                que.pop_back();
            }
            que.push_back(nums[i]);
            //最大值输入ans
            ans.push_back(que.front());
        }
        return ans;
    }
};

0 赞同 0 条回复

NullPointerException 普通 2023年8月3日下午4:56

class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
//最小队列单调队列队列只能单调递减双端队列
Deque deque =new LinkedList(); //里面记录nums的下标
if(nums.length1) return new int[]{nums[0]};

for(int i=0;i<k;i++)
{
    maxqueue(deque,nums[i],i,nums,k);
}
int result[] =new int[nums.length-k+1];
int j=0;
result[j++]=nums[deque.peekFirst()];
for(int i=k;i<nums.length;i++)
{
    maxqueue(deque,nums[i],i,nums,k);
    result[j++]=nums[deque.peekFirst()];
}
    return result;
}

public void maxqueue(Deque deque,int num,int i,int nums[],int k)
{
    if(deque.isEmpty())
    {
        deque.add(i);
    }else
    {
        if((int)deque.peekFirst()==i-k) //上一个正好是最大值 移除
        {
            deque.removeFirst();
        }
        if(deque.isEmpty())
    {
        deque.add(i);
    }else 
    {
        if(num>=nums[(int)deque.peekFirst()])//如果 新来的元素比队列中的都大
        {
            deque.clear();
            deque.addFirst(i);
        }else{
            while(num>=nums[(int)deque.peekLast()])
            {
                deque.removeLast();
            }
            deque.addLast(i);
        }
    }
}

}
}

0 赞同 0 条回复

Marshan 普通 2023年8月3日下午12:21

写滑动窗口的题目,思路要清晰,细节要考虑到位

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

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

        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 条回复

Mby 普通 2023年8月2日下午9:03

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;

        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(k)
    }
}

0 赞同 0 条回复

Luminous 普通 2023年8月1日下午12:56

以下是代码

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums==null||nums.length==1){
            return nums;
        }
        LinkedList<Integer> q=new LinkedList<>();
        int index=0;
        int[] res=new int[nums.length-k+1];
        for(int i=0;i<nums.length;i++){
            while(!q.isEmpty()&&nums[q.peekLast()]<nums[i]){
                q.pollLast();
            }
            q.add(i);
            if(q.peekLast()-q.peek()==k){
                q.poll();
            }
            if(i+1>=k){
                res[index++]=nums[q.peek()];
            }
        }
        return res;
    }
}

0 赞同 0 条回复

AD钙奶普通 2023年7月31日下午3:32

但用双指针进行滑动窗口，对于窗口过大的测试用例来说，会超时。
解决方案：加入单调队列来维护。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if (n * k == 0) return new int[0];
        if (k == 1) return nums;

        Deque<Integer> deque = new ArrayDeque<>();
        int[] res = new int[n - k + 1];
        int maxIndex = 0;

        for (int i = 0; i < n; i++) {
            // 检查队列的头部索引是否已经超出当前窗口的范围
            if (!deque.isEmpty() && deque.peek() < i - k + 1) {
                deque.poll();
            }
            // 检查队列的尾部索引对应的元素是否小于等于 nums[i]
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            // 将 i 添加到队列的尾部
            deque.offer(i);
            // 如果 i 大于等于窗口的大小 k-1，表示窗口已经形成
            if (i >= k - 1) {
                // 将队列头部的索引对应的元素加入结果列表
                res[maxIndex++] = nums[deque.peek()];
            }
        }
        return res;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年7月31日下午2:55

public int[] maxSlidingWindow(int[] nums, int k) {
    //输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
    //输出: [3,3,5,5,6,7]
    List<Integer> res = new ArrayList<>();
    for (int l=0,r=0;l<nums.length&&r<nums.length;r++) {
        if (r-l+1 == k) {
            int choice = Integer.MIN_VALUE;
            for (int i = l; i <= r; i++) {
                if (nums[i] > choice) {
                    choice = nums[i];
                }
            }
            res.add(choice);
            l++;
        }
    }
    return res.stream().mapToInt(Integer::intValue).toArray();
}

0 赞同 0 条回复

人生何处不青山普通 2023年7月30日下午11:25

单调队列经典题目

function maxSlidingWindow(nums: number[], k: number): number[] {
    let queue = [];
    let hh = 0, tt = -1;
    let res = [];
    for (let i = 0; i < nums.length; i++) {
        while(hh <= tt && (queue[hh] + k) <= i) hh++;
        while(hh <= tt && nums[queue[tt]] < nums[i]) tt--;
        queue[++tt] = i;
        if( i >= k - 1) res.push(nums[queue[hh]]);
    }
    return res;
};

0 赞同 0 条回复

长河呼叫黄江普通 2023年7月30日下午9:49

7.30
Day21：下面是代码

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

0 赞同 0 条回复

阿尚普通 2023年7月30日下午7:55

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        List<Integer> list = new ArrayList<>();
        Deque<Integer> dq = new LinkedList<>();//单调队列存储元素的位置

        for(int i = 0; i < nums.length; i++){
            if(!dq.isEmpty() && i - dq.peekFirst() > k - 1){
                dq.pollFirst();
            }
            while(!dq.isEmpty() && nums[i] > nums[dq.peekLast()]){
                dq.pollLast();
            }
            dq.offerLast(i);

            if(i >= k - 1) list.add(nums[dq.peekFirst()]);
        }

        int[] res = new int[list.size()];

        for(int i = 0; i < list.size(); i++){
            res[i] = list.get(i);
        }

        return res;
    }
}

0 赞同 0 条回复

【数学知识】剑指 Offer 59 – I. 滑动窗口的最大值

共以下 16 个回答

# 回答此问题取消回复

【数学知识】剑指 Offer 59 – I. 滑动窗口的最大值

共以下 16 个回答

# 回答此问题 取消回复

# 回答此问题取消回复