九号球普通 2023年11月25日上午9:49

“`java
暴力
class Solution {
public int[] maxAltitude(int[] heights, int limit) {
if (heights == null || heights.length == 0) {
return new int[0];
}
int length = heights.length;
int[] res = new int[length – limit + 1];
for (int i = 0; i < length - limit + 1; i++) { int max = Integer.MIN_VALUE; for (int k = i; k < limit + i; k++) { if (heights[k] > max) {
max = heights[k];
}
}
res[i] = max;
}
return res;
}
}

0 赞同 0 条回复

招舟子普通 2023年9月8日上午1:45

class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
//用单调队列
int[] res = new int[nums.length-k+1];
int index =0;
LinkedList list = new LinkedList<>();
for(int i=0;i<nums.length;i++){
while(!list.isEmpty()&&nums[list.peekLast()]<nums[i]){
list.pollLast();
}
list.add(i);
if(list.peekLast()-klist.peek()){
list.poll();
}
if(i+1>=k){
res[index++]=nums[list.peek()];
}

    }
    return res;

}
}
单调队列解决滑动窗口最大值问题

0 赞同 0 条回复

桀桀桀Jay 普通 2023年8月3日下午12:06

java
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length <= 1) {
            return nums;
        }

        Deque<Integer> res = new LinkedList<>();
        int[] arr = new int[nums.length - k + 1];  //存储最终结果
        int index = 0;

        //未形成窗口前
        for(int i = 0; i < k; i++) {
            while(!res.isEmpty() && nums[i] > res.peekLast()) {
                res.removeLast();
            }
            res.addLast(nums[i]);
        }

        arr[index++] = res.peekFirst();
        //形成窗口后，i指向窗口的最后元素
        for(int i = k; i < nums.length; i++) {
            if(res.peekFirst() == nums[i-k]) {
                res.removeFirst();
            }

            while(!res.isEmpty() && nums[i] > res.peekLast()) {
                res.removeLast();
            }
            res.addLast(nums[i]);
            arr[index++] = res.peekFirst();
        }
        return arr;
    }
}

时间复杂度是O(k*N), 空间复杂度是O(k)

0 赞同 0 条回复

屠龙手段普通 2023年7月27日下午11:05

双端队列，时间复杂度O(n) 空间复杂度O(k)

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if k == 1: return nums
        deque = collections.deque()
        res = []
        for i, j in zip(range(1 - k, len(nums) - k + 1), range(len(nums))):
            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 条回复

怀瑾永久会员 2023年7月19日下午3:39

“`C++
vector maxSlidingWindow(vector& nums, int k) {
vector result;
deque window; // 存放窗口中的元素索引

for (int i = 0; i < nums.size(); i++) {
    // 如果窗口中的元素已经超出窗口大小的范围，则移除窗口最左边的元素
    while (!window.empty() && window.front() <= i - k)
        window.pop_front();

    // 从窗口尾部开始，移除所有小于当前元素的索引
    while (!window.empty() && nums[i] >= nums[window.back()])
        window.pop_back();

    // 将当前元素的索引加入窗口
    window.push_back(i);

    // 当窗口大小达到k时，将窗口最左边的元素加入结果
    if (i >= k - 1)
        result.push_back(nums[window.front()]);
}

return result;

}

“`

0 赞同 0 条回复

名字什么的好麻烦普通 2023年7月17日下午10:17

队列

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        LinkedList<Integer> queue = new LinkedList<>();
        int[] result = new int[nums.length-k+1];
        for(int i=0;i<nums.length;i++){
            while(!queue.isEmpty() && nums[queue.peekLast()]<=nums[i])
                queue.pollLast();
            queue.offer(i);
            if(queue.peekFirst()<=i-k)
                queue.poll();
            if(i+1>=k)
                result[i-k+1]=nums[queue.peek()];
        }
        return result;
    }
}

0 赞同 0 条回复

江畅普通 2023年7月16日下午2:56

// 滑动窗口的最大值
// 时间复杂度 O(N)
// 空间复杂度 O(k)
class Solution {

private:
    // 创建一个数据结构维护滑窗元素（非全部元素，只需能获取滑窗最大元素）
    // deque 实现, 队头为滑窗最大元素
    class MonotonicQueue {
        private:
            deque<int> maxq;  // 底层由 deque 实现
        public:

            // 添加元素
            void push(int val) {
                // 将小于添加值的元素弹出
                while (!maxq.empty() && maxq.back() < val) {
                    maxq.pop_back();
                }
                maxq.push_back(val);
            }

            // 弹出元素, 移出滑窗最左边的值
            // 只维护滑窗最大值, 故只在滑窗最左边值为当前窗口最大值时才进行操作
            void pop(int val) {
                if (val == maxq.front()) {
                    maxq.pop_front();
                }
            }

            int front() {
                return maxq.front();
            }
    };

public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;

        MonotonicQueue slidingWindow;

        // 初始窗口元素入队
        for (int i = 0; i < k; ++i) {
            slidingWindow.push(nums[i]);
        }

        res.push_back(slidingWindow.front());

        // 滑窗
        for (int j = k; j < nums.size(); ++j) {
            slidingWindow.pop(nums[j - k]);
            slidingWindow.push(nums[j]);
            res.push_back(slidingWindow.front());
        }
        return res;
    }
};

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年7月16日上午6:50

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q = deque()
        res = []

        for i in range(len(nums)):
            while q and nums[q[-1]] <= nums[i]:
                q.pop()

            q.append(i)

            if q[0] == i - k:
                q.popleft()

            if i >= k - 1:
                res.append(nums[q[0]])

        return res

滑动窗口加 deque

0 赞同 0 条回复

BOZ 普通 2023年7月16日上午12:12

【思路】用一个额外的list维护max candidate，每次window向右移则从队头取出最大（如果和被discard的元素相同）并将新元素添加至队尾（先删除队尾所有小于它的元素）
【复杂度】这种方法对于k较大的case来说比较友好，使得时间复杂度降低（从O(nk)降低为O(n))，但（因为无法对传入的nums数组做inplace运算，会导致空间复杂度的上升（从O(1)上升为O(n)）

class Solution {
public:
    vector maxSlidingWindow(vector& nums, int k) {
        std::deque l;
        std::vector result(nums.size() - k + 1);
        for (int i = 0; i < nums.size(); i++) {
            // remove the last element
            if (i >= k && nums[i - k] == l.front()) l.pop_front();

            // add new element
            while (!l.empty() && l.back() < nums[i]) l.pop_back();
            l.push_back(nums[i]);

            // record the max for this window
            if (i >= k - 1) result[i - k + 1] = l.front();
        }
        return result;
    }
};

0 赞同 0 条回复

花老爷普通 2023年7月15日下午1:11

官解单调队列
时间：O(n)
空间：O(n)

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> deque = new LinkedList<Integer>();
        for (int i = 0; i < k; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
        }

        int[] ans = new int[n - k + 1];
        ans[0] = nums[deque.peekFirst()];
        for (int i = k; i < n; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            while (deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }
            ans[i - k + 1] = nums[deque.peekFirst()];
        }
        return ans;
    }
}

0 赞同 0 条回复

Ming 普通 2023年7月14日下午8:04

思路：建立队列存放可能成为最大元素的下标，如果当前元素从尾到头比较小于他的都去掉，
当i – k queue.peek()时去掉头，当i + 1 >= 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.getLast()] < nums[i]) {
                queue.removeLast();
            }
            queue.offer(i);
            if(i - k == queue.peek()) {
                queue.poll();
            } 
            if(i + 1 >= k) {
                res[index++] = nums[queue.peek()];
            }

        }
        return res;
    }
}

0 赞同 0 条回复

行动派小彩笔普通 2023年7月13日下午7:37

/// 额外空间最大尾O(k),时间复杂度最大O(kn)
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if(nums.empty ||nums.size()<k) return {};
        vector<int> ans;
        deque<int> q; //队头到队尾，是从大到小
        for(int i = 0;i<nums.size();++i)
        {
            while(!q.empty()&& nums[q.back()]<=nums[i])   // while结束 nums[q.back()] >nums[i]
                q.pop_back();  
            q.push_back(i);

            // 滑动窗口，没k次换一个最大元素
            if(q.front()==i-k)  //表示队头已经不在窗口范围了
                q.pop_front();
            if(i+1>=k)
                ans.push_back(nums[q.front()]);
        }
        return ans;

    }
};

0 赞同 0 条回复

Vow the vow。普通 2023年7月12日上午11:36

维护一个自己的单调队列。

// 维持一个单调队列
    class MyDeque{
        Deque<Integer> deque;

        MyDeque(){
            deque  = new LinkedList<>();
        }

        private int peek(){
            return deque.peekFirst();
        }

        private void add(int val){
            while(!deque.isEmpty() && deque.peekLast() < val){
                deque.pollLast();
            }
            deque.addLast(val);
        }

        private void poll(int val){
            if(deque.peekFirst() == val){
                deque.pollFirst();
            }
        }
    }

    public int[] maxSlidingWindow(int[] nums, int k) {
        int l = 0,r = 0;
        int n = nums.length;
        MyDeque mydeque = new MyDeque();
        while(r < k){
            mydeque.add(nums[r++]);
        }
        List<Integer> res = new ArrayList<>();
        while(r < n){
            res.add(mydeque.peek());
            mydeque.add(nums[r]);
            mydeque.poll(nums[l]);
            l++;
            r++;
        }
        res.add(mydeque.peek());
        int[] res2 = new int[res.size()];
        for(int i = 0;i < res.size(); i++){
            res2[i] = res.get(i);
        }
        return res2;
    }

0 赞同 0 条回复

mpweixin用户永久会员 2023年7月12日上午12:38

public int[] maxSlidingWindow(int[] nums, int k) {
        //用双端队列来保存"备选人"---有可能是最大值的数
        //当窗口移动时，某个最大值不在窗口，应当从备选人中选出一个最大值
        Deque<Integer> deque = new LinkedList<>();
        int[] result = new int[nums.length - k + 1];

        for(int i = 0;i < nums.length;i++){

            //小的都出去，有我在，最大值就不可能是你们
            //每一个数都有可能成为最大值，因为窗口在移动
            while(!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]){
                deque.pollLast();
            }
            //自己进去
            deque.offer(i);

            //保证当前队列头的元素是有效的
            if(!deque.isEmpty() && (i - deque.peek()) >= k){
                //队顶元素已经不在窗口内
                deque.poll();
            }

            //此时队顶元素是当前窗口最大值
            if(i >= k - 1){ //i指向k-1时，才形成一个长度为k的窗口，开始记录
                result[i - k + 1] = nums[deque.peek()];
            }

        }
        return result;
    }

0 赞同 0 条回复

张君雅小妹妹普通 2023年7月11日下午9:50

时间复杂度：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);

            if(queue.peekLast() - queue.peek() == k) {
                queue.poll();
            }

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

0 赞同 0 条回复

yxy 普通 2023年7月11日下午8:19

时间复杂度O(n)

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.size()&&nums[i]>=nums[q.back()])
            {
                q.pop_back();
            }
            q.push_back(i);
            if(i<k-1)
            {
                continue;
            }
            if(q.front()<=i-k)
                q.pop_front();
            res.push_back(nums[q.front()]);
        }
        return res;
    }
};

0 赞同 0 条回复

Dsjh 普通 2023年7月11日下午3:51

MY

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ans;
        deque<int> q;
        for(int i=0;i<nums.size();i++){
            // 先维护 队列的大小，不能大于窗口大小
            while(!q.empty() && i-q.front()+1 > k){
                q.pop_front();
            }
            // 再维护队列的单调性，队头最大
            while(!q.empty() && nums[i]>nums[q.back()]){
                q.pop_back();
            }
            q.push_back(i);
            //
            if(i+1>=k){
                ans.push_back(nums[q.front()]);
            }
        }
        return ans;
    }
};

0 赞同 0 条回复

Yodl. 普通 2023年7月11日下午3:50

//单调队列或单调栈：维护一个队列。始终保持队头元素是当前遍历窗口中对应的最大元素的下标。
//这样的话，可以直接在O(1)的时间复杂度取到当前窗口中最大的元素
//时间复杂度O(n) 空间复杂度O(k)
class Solution {
public:
    vector maxSlidingWindow(vector& nums, int k) {
        vector ans;
        deque q;

        for (int i = 0; i < nums.size(); i++) {
            if (q.size() && q.front() <= i - k) q.pop_front();
            while (q.size() && nums[q.back()] <= nums[i]) q.pop_back();
            q.push_back(i);
            if (i >= k - 1) ans.push_back(nums[q.front()]);
        }

        return ans;
    }
};

0 赞同 0 条回复

张开怀普通 2023年7月11日下午3:48

class Solution{
public:
       vector<int> maxSlidingWindow(vector<int>& nums, int k){
              if(nums.empty() || nums.size()<k){
                     return vector<int>();
              }
              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;
       }
};

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

0 赞同 0 条回复

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

共以下 19 个回答

MY

# 回答此问题取消回复

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

共以下 19 个回答

MY

# 回答此问题 取消回复

# 回答此问题取消回复