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

共以下 5 个回答

• sincere 普通 2023年9月10日 下午11:40

  • 思路：看题解用双端队列维护了一个单调递减的队列
  • 复杂度：时间复杂度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> queue = new LinkedList<>();
          int[] res = new int[nums.length - k + 1];
          // 未形成窗口
          for (int i = 0; i < k; i++) {
              while (!queue.isEmpty() && queue.peekLast() < nums[i]) {
                  queue.removeLast();
              }
              queue.addLast(nums[i]);
          }
          res[0] = queue.peekFirst();
          // 形成窗口后
          for (int i = k; i < nums.length; i++) {
              if (queue.peekFirst() == nums[i - k]) {
                  queue.removeFirst();
              }
              while (!queue.isEmpty() && queue.peekLast() < nums[i]) {
                  queue.removeLast();
              }
              queue.addLast(nums[i]);
              res[i - k + 1] = queue.peekFirst();
          }
          return res;
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 小肸 永久会员 2023年9月10日 上午11:14

  class Solution {
      public int[] maxSlidingWindow(int[] nums, int k) {
          //使用双端队列维持一个单调队列，队首的元素就是窗口的最大值
          //第一个问题: 队首的元素怎么判断是否属于窗口中
          //解决方法一: 下标法，队列中存储是元素的下标
          //解决方法二: 每次移动窗口时，判断队首元素是不是窗口移除的元素
          //时间复杂度O(N)，空间复杂度O(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.pollLast();
              }
              deque.offerLast(nums[i]);
          }
          res[0] = deque.peekFirst();
          for (int i = k; i < nums.length; i ++) {
              if (!deque.isEmpty() && deque.peekFirst() == nums[i - k]) {
                  deque.pollFirst();
              }
              while (!deque.isEmpty() && deque.peekLast() < nums[i]) {
                  deque.pollLast();
              }
              deque.offerLast(nums[i]);
              res[i - k + 1]  = deque.peekFirst();
          }
          return res;
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 行动派小彩笔 普通 2023年9月4日 下午10:19

  // 单调栈，时间复杂度O(n),空间复杂度O(k)
  class Solution {
  public:
      vector<int> maxSlidingWindow(vector<int>& nums, int k) {
          vector<int> res;
          deque<int> q;
          for(int i=0;i<nums.size();i++)
          {
              while(!q.empty() && nums[q.back()]<nums[i])
                  q.pop_back();
              q.push_back(i);
              if(i-q.front()==k)
                  q.pop_front();
              if(i>=k-1)
                  res.push_back(nums[q.front()]);
          }
          return res;
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• 塔底的仰望 永久会员 2023年9月4日 下午8:09

  看题解了

  class Solution {
      public int[] maxSlidingWindow(int[] nums, int k) {
         if(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;
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• JustRtn 普通 2023年9月4日 下午5:09

  使用双端队列保存可能的最大值的下标。
  遍历：当前元素（下标对应值）大于队列尾元素（下标对应值），将该队尾元素出队，循环；
  当队列头元素不在窗口内了，将该队头元素出队；
  保存当前窗口最大值（对头元素对应值）；

  class Solution {
  public:
      vector<int> maxSlidingWindow(vector<int>& nums, int k) {
          if (nums.empty() || nums.size() < k) {
              return {};
          }
          deque<int> dq;
          vector<int> vec;
          for (int i = 0; i < nums.size(); i++) {
              while (!dq.empty() && nums[i] >= nums[dq.back()]) {
                  dq.pop_back();
              }
              dq.push_back(i);
              if (dq.front() == i - k) {
                  dq.pop_front();
              }
              if (i >= k - 1) {
                  vec.push_back(nums[dq.front()]);
              }
          }
          return vec;
      }
  };
  

  0 赞同 0 条回复

  登录以回复