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

宁永久会员 2023年3月16日下午9:50

借助双端队列实现，栈顶元素为最大值

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        //deque 双端队列
        //遇到比他大的前面就出栈，比他小的就放在里面，超过窗口长度则出队列，每次记录栈顶元素
        int[] res = new int[nums.length - k + 1];
        Deque<Integer> queue = new LinkedList<>();
        for(int i = 0; i < nums.length; i++){
            while(!queue.isEmpty() && nums[i] > nums[queue.peekLast()]){
                queue.pollLast();
            }
            queue.offer(i);
            if(queue.peekLast() - queue.peekFirst() == k){
                queue.poll();
            }
            if(i >= k - 1){
                res[i - k + 1] = nums[queue.peek()];
            }
        }
        return res;
    }
}

0 赞同 0 条回复

PatNick 普通 2023年1月13日上午10:37

def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # 维护一个队列，放入那些可能为最大值元素的下标,初始值为第一个元素索引

        queue = []
        res = []

        for _ in range(len(nums)):
            # 判断队列结尾的元素如果小于等于当前元素要删除
            while queue and nums[queue[-1]] <= nums[_]:
                queue.pop(-1)

            queue.append(_)

            if queue[-1] - k == queue[0]:
                queue.pop(0)

            if _ +1 >= k:
                res.append(nums[queue[0]])


        return res

0 赞同 0 条回复

lucca 普通 2023年1月13日上午12:24

双指针

时间复杂度 O(N)
空间复杂度 O(N)

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] ans = new int[nums.length - k + 1];

        int[] q = new int[nums.length];
        int hh = 0, tt = -1;

        for (int i = 0; i < k - 1; i++) {
            if (hh <= tt && q[hh] <= i - k) hh++;
            while (hh <= tt && nums[q[tt]] <= nums[i]) tt--;
            q[++tt] = i;
        }
        for (int i = k - 1; i < nums.length; i++) {
            if (hh <= tt && q[hh] <= i - k) hh++;
            while (hh <= tt && nums[q[tt]] <= nums[i]) tt--;
            q[++tt] = i;
            ans[i - k + 1] = nums[q[hh]];
        }
        return ans;
    }
}

0 赞同 2 条回复

shuaidi 永久会员 @ lucca 2023年1月13日上午1:01

这么晚还在打卡啊

登录以回复
lucca 普通 @ shuaidi 2023年1月17日上午12:38

hh，网课刷不动了，来刷刷题

登录以回复

庄重普通 2023年1月6日上午9:33

// 思路：
//     1.使用双端队列辅助
//     2.保证队列头部永远是最大值
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> deq_int;
        vector<int> ret;

        for(int i = 0; i < nums.size(); i++){
            //队列中头部默认是最大的，要删除需要从后向前删除，也只有这里需要删除尾部，用queue也可以的,需要另一个queue进行辅助
            while(!deq_int.empty() && nums[deq_int.back()] < nums[i]){
                deq_int.pop_back();
            }

            deq_int.push_back(i);
            //超出滑动窗口大小进行pop
            if(deq_int.back() - k == deq_int.front()){
                deq_int.pop_front();
            }

            if(i + 1 >= k){
                ret.push_back(nums[deq_int.front()]);
            }
        }
        return ret;
    }
};
// 时间复杂度O(n)
// 空间复杂度O(n)

0 赞同 0 条回复

yanshuojune 普通 2022年12月7日下午9:54

时间：O（n）
空间：O(n)

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # 队列
        n = len(nums)
        q = collections.deque()
        for i in range(k):
            while q and nums[i] >= nums[q[-1]]:
                q.pop()
            q.append(i)
        ans = [nums[q[0]]]
        for i in range(k,n):
            while q and nums[i] >= nums[q[-1]]:
                q.pop()
            q.append(i)
            while q[0] <= i - k:
                q.popleft()
            ans.append(nums[q[0]])
        return ans

0 赞同 0 条回复

symbol 普通 2022年12月3日上午7:32

func reverseLeftWords(s string, n int) string {
    b := []byte(s)
    // 1. 反转前n个字符
    // 2. 反转第n到end字符
    // 3. 反转整个字符
    reverse(b, 0, n-1)
    reverse(b, n, len(b)-1)
    reverse(b, 0, len(b)-1)
    return string(b)
}
// 切片是引用传递
func reverse(b []byte, left, right int){
    for left < right{
        b[left], b[right] = b[right],b[left]
        left++
        right--
    }
}

0 赞同 0 条回复

🚲南下普通 2022年12月2日下午2:54

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if(nums.empty()) return {};
        vector<int> ans;
        priority_queue<pair<int,int>> que;
        int len = nums.size(); //初始化优先级队列
        for(int i = 0; i < k;i++) que.emplace(nums[i],i);

        ans.push_back(que.top().first);
        for(int i = k; i < len; i++){
            que.emplace(nums[i],i);
            while(que.top().second < i-k+1) que.pop(); //开始淘汰
            ans.push_back(que.top().first);
        }
        return ans;
    }
};

0 赞同 0 条回复

波波_1936 普通 2022年11月24日下午6:05

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

        if (nums == null || nums.length == 0) return new int[0];
        //双指针方式
       /* List<Integer> res = new ArrayList<>();
        int left = 0;
        int right = k - 1;//index
        while (right < nums.length) {
            int max = Integer.MIN_VALUE;
            for (int i = left; i <= right; i++) {
                max = Math.max(max, nums[i]);
            }
            res.add(max);
            left++;
            right++;
        }
        return res.stream().mapToInt(Integer::valueOf).toArray();*/


        //滑动窗口 双端队列

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


        }
        return res;


    }

0 赞同 0 条回复

是梦终空永久会员 2022年11月23日下午11:09

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

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

        LinkedList<Integer> que = new LinkedList<>();   //定义队列  来存放nums下标值
        int[] res = new int[nums.length - k+1];     //定义数组
        int index = 0;                              //数组的索引  
        for(int i = 0;i<nums.length;i++){              //循环遍历nums

            while( !que.isEmpty() && nums[que.peekLast()] <= nums[i]){  //将小于新入栈的的元素全部出栈，因为他们无法再成为最大值
                que.pollLast();
            }

            que.add(i);                                     //添加元素下标

            if(que.peekLast() - k == que.peek()){           //这个if 用来判断如果队列中的值超过滑动窗口的大小，就把栈底的元素出队
                que.poll();                                 
            }
            if(i + 1 >= k){                                 //当队列的元素 == k 时，将栈顶元素赋给res数组
                res[index++] = nums[que.peek()];            //
            }
        }
        return res;
    }
}

0 赞同 0 条回复

天然普通 2022年11月21日下午8:12

双向队列，移动去取最大值，时间复杂度O(n)，空间复杂度 O(k)

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        deque = collections.deque()
        res ,n = [],len(nums)
        for i,j in zip(range(1-k,n+1-k),range(n)):
            if i>0 and deque[0]==nums[i-1]:
                deque.popleft()
            while deque and  deque[-1] < nums[j]:
                deque.pop()
            deque.append(nums[j])
            if i>=0:
                res.append(deque[0])
        return res

0 赞同 0 条回复

你有点可爱喔普通 2022年11月21日下午3:26

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length<=1){
            return nums;
        }
        LinkedList<Integer> queue = new LinkedList<>();
        int [] num = new int[nums.length-k+1];
        int count = 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){
                num[count++] = nums[queue.peek()];
            }
        }
        return num;
    }
}

0 赞同 0 条回复

@ 普通 2022年11月21日上午10:40

class Solution {
    //暴力解法（超出时间限制）
    //时间复杂度O(nk)
    //空间复杂度 O(1)
    public int[] maxSlidingWindow(int[] nums, int k) {
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i <= nums.length - k; i++) {
            int max = Integer.MIN_VALUE;

            for (int j = i; j < i + k; j++) {
                if (nums[j] > max) {
                    max = nums[j];
                }

            }

            list.add(max);

        }

        int[] res = list.stream().mapToInt(Integer::valueOf).toArray();

        return res;

    }

    //使用队列
    //时间复杂度O(n)
    //空间复杂度 O(k)
    public int[] maxSlidingWindow2(int[] nums, int k) {
        if (nums.length == 0 || k == 0) return new int[0];
        Deque<Integer> deque = new LinkedList<>();
        List<Integer> list = new ArrayList<Integer>();
        // 未形成窗口
        for (int i = 0; i < k; i++) {
            while (!deque.isEmpty() && deque.peekLast() < nums[i])
                deque.removeLast();
            deque.addLast(nums[i]);
        }
        list.add(deque.peekFirst());
        // 形成窗口后
        for (int i = k; i < nums.length; i++) {
            if (deque.peekFirst() == nums[i - k])
                deque.removeFirst();
            while (!deque.isEmpty() && deque.peekLast() < nums[i])
                deque.removeLast();
            deque.addLast(nums[i]);
            list.add(deque.peekFirst());
        }
        return list.stream().mapToInt(Integer::valueOf).toArray();
    }


}

0 赞同 0 条回复

lobort 普通 2022年11月19日下午8:09

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        //方法一 滑动窗口 但是时间超了
        int left = 0, right = k - 1;
        int[] res = new int[nums.length - k + 1];
        int max = nums[0];
        while(right <= nums.length - 1){
            for(int i = left; i < right + 1; i++){
                max = Math.max(max, nums[i]);
            }
            res[left] = max;
            right++;
            left++;
            max = nums[left];
        }
        return res; 

        //方法二 优先队列 
        int[] res = new int[nums.length - k + 1];
        LinkedList<Integer> queue = new LinkedList<>();
        int cur = 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[cur++] = nums[queue.peek()];
            }
        }
        return res;
    }
}

0 赞同 0 条回复

派大星普通 2022年11月19日上午11:50

class Solution {
//通过使用一个集合，使有可能成为最大值的数进入集合，控制集合元素的范围，使新加入的数在数组的位置减去集合的首位数的值小于滑
//动窗口的范围
//时间复杂度O(n)
//空间复杂度O(k)
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums == null || nums.length <= 1 || k == 1) return nums;
        LinkedList<Integer> queue = new LinkedList<>();
        int[] values = 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(i - queue.peekFirst() == k) queue.pollFirst();         //654321
              if(i >= k - 1){
                  values[index++] = nums[queue.peekFirst()];
              }

        }
        return values;
    }
}

0 赞同 0 条回复

大宝子冲永久会员 2022年11月17日下午8:17

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)
想半天。。。看了视频解析也想半天。。。

0 赞同 0 条回复

易水寒永久会员 2022年11月17日上午9:48

思路类似于单调栈

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> deque = new LinkedList<>();
        int[] res = new int[nums.length-k+1];
        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 < nums.length; 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 条回复

訁訁訁訁訁普通 2022年11月17日上午12:25

//自己写的暴力，超时
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        List<Integer> list = new ArrayList<>();
        for(int i = 0;i <= nums.length - k;i++){
            int max = Integer.MIN_VALUE;
            for(int j = i;j < i+k;j++){
                   max = Math.max(max,nums[j]);
            }
            list.add(max);
        }
        return list.stream().mapToInt(Integer::valueOf).toArray();
    }
}

时间复杂度O(n)空间复杂度O(k)最多维护k个元素

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums == null || nums.length <= 1){
            return nums;
        }
        int len = nums.length;
        //队首维护最大值
        LinkedList<Integer> deque = new LinkedList<>();
        int[] ret = new int[len - k + 1];
        int index = 0;
        for(int i = 0;i < len;i++){
            //单调队列,队列为空或出现新元素大于当前维护窗口的最小值
            while(!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]){
                deque.pollLast();
            }
            deque.add(i);
            //新加入元素后，窗口满了，溢出队首元素
            if(deque.peekLast() - deque.peek() == k){
                deque.poll();
            }
            //i遍历到第一个窗口的右边界
            if(i + 1 >= k){
                ret[index++] = nums[deque.peek()];
            }
        }
        return ret;

    }

0 赞同 0 条回复

mpweixin用户普通 2022年11月16日下午7:04

第一道题

“`c++
class Solution {
public:
vector> findContinuousSequence(int target) {
int sum = 1;
vector> ans;
int i = 1, j = 1;
while(i*2 < target) { if(sum < target) { j++; sum += j; }else if(sum > target) {
sum -= i;
i++;
} else {
vector temp;
for(int k = i; k <= j; k++) { temp.push_back(k); } ans.push_back(temp); sum -= i; i++; j++; sum += j; } } return ans; } };

第二道题
```c++
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        priority_queue<pair<int, int>> q;
        if(nums.size() == 0) return nums;
        for(int i = 0; i < k; ++i) {
            q.emplace(nums[i], i);
        }
        vector<int> ans = {q.top().first};
        for(int i = k; i < n; ++i) {
            q.emplace(nums[i], i);
            while(q.top().second <= i - k) {
                q.pop();
            }
            ans.push_back(q.top().first);
        }
        return ans;
    }
};

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月16日下午6:03

时间复杂度为O（n），空间复杂度为O（k）

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);
            while(queue.peek() + k == queue.peekLast()){
                queue.poll();
            }
            if(i + 1 >= k){
                res[index++] = nums[queue.peek()];
            }
        }
        return res;
    }
}

0 赞同 0 条回复

T 普通 2022年11月16日下午5:57

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];
        // 第一个窗口，前k个
        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 < nums.length; i++) {
            //窗口移动，如果移除的那个数正好是队列的头节点则要弹出。
            if(nums[i - k] == deque.peekFirst())
                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 条回复

So 普通 2022年11月16日上午10:27

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

just 普通 2022年11月16日上午10:12

//数据结构
class Solution {
public:
class mydata{
public:
deque que;
void push(int val){
while(!que.empty()&&val>que.back()) que.pop_back();
que.push_back(val);
}
void pop(int val){
if(valque.front()) que.pop_front();
}
int front(){
return que.front();
}
};
vector maxSlidingWindow(vector& nums, int k) {
mydata que;
for(int i=0;i<k-1;++i) que.push(nums[i]);
vector res;
for(int i=k-1;i<nums.size();++i){
que.push(nums[i]);
res.push_back(que.front());
que.pop(nums[i-k+1]);
}
return res;

};

0 赞同 0 条回复

青木普通 2022年11月15日下午11:23

/**
    不会...
    用一个单调栈维护当前窗口从大到小的数
    窗口移动时，如果最左边的是最大值，则将deque左端出列
    当遍历的值大于deque右端，则将deque右端出列
    将deque的左端加入答案

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

 */

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[] ans = new int[nums.length - k + 1];
        //实现第一个窗口
        for(int i=0; i<k; i++){
            while(!deque.isEmpty() && deque.peekLast() < nums[i]){
                deque.removeLast();
            }
            deque.addLast(nums[i]);
        }

        ans[0] = deque.peekFirst();

        for(int i=k; i<nums.length; i++){
            if(nums[i-k] == deque.peekFirst()){
                deque.removeFirst();
            }
            while(!deque.isEmpty() && deque.peekLast() < nums[i]){
                deque.removeLast();
            }
            deque.addLast(nums[i]);
            ans[i-k+1] = deque.peekFirst();
        }
        return ans;
    }
}

0 赞同 0 条回复

Error 普通 2022年11月15日下午10:48

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        stack = []
        res = []
        m = 0
        for i in range(k):
            while stack and stack[-1] < nums[i]:
                stack.pop(-1)
            stack.append(nums[i])
        res.append(stack[0])

        for i in range(k, len(nums)):
            if nums[i-k] == stack[0]:
                stack.pop(0)
            while stack and stack[-1] < nums[i]:
                stack.pop(-1)
            stack.append(nums[i])
            res.append(stack[0])
        return res

时间复杂度 O(n)

0 赞同 0 条回复

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

共以下 24 个回答

双指针

# 回答此问题取消回复

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

共以下 24 个回答

双指针

# 回答此问题 取消回复

# 回答此问题取消回复