这么简单的题目我居然搞了两个小时。。。 题目 题目描述： 给一个长度为N的数组，一个长为K的滑动窗体从最左端移至最右端，你只能看到窗口中的K个数，每次窗体向右移动一位，如下图： 你的任务是找出窗体在各个位置时的最大值和最小值。
展开全文
读完题第一感是multiset，写完之后提交，内存超出限制。然后码了个线段树，内存超出限制。之后去网上搜了相关知识点，才知道这是典型的单调队列题目。用一个deque维护一个单调增的队列，这样队尾一定是最小值。维护方法如下：如果新增一个元素，首先和队首进行比较，如果不大于队首，则队首出队，重复这个过程
展开全文
常规做法当然是单调队列，但我全都要。 单调队列 Solution 求最大值和最小值的方法实际上是一样的。 这里只以求最大值为例： 从左往右扫到某一个值的时候，如果当前值的大小比前面的某些值要大的时候，结尾是当前位置往右的的最大值就不可能是前面比当前值小的。 还有一种情况是队头已经超出这个区间范围了，
展开全文
Solution Code #pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 1
展开全文
描述见题面思路：单调队列，遍历所有元素，并维护一个队列（以最大值为例），此队列中，队头表示的是当前窗口内的最大值，其他的是可能成为最大值的候选，并且越在队列的后面生命周期越长，假设当前遍历到了下标为 i 的元素，那么首先要检验一下队列中那个“最老”的元素，即队头还在不在窗口范围内，若不在就弹出，因为
展开全文
按着题意直接模拟就好~先说下思路8 31 3 -1 -3 5 3 6 7从样例开始,用最小值来说吧..因为最小值比最大值的方法更明显..我们从第一个开始处理,第一个有没有可能是最小值,当然可能,因为前面不存在嘛~到了第二个数,第二个数有没有可能是最小值,当然也是可能的,因为前面的那个虽然比它小,但是
展开全文
题意：给定一个长度为n的序列和长度为k的窗口，求每次窗口滑动时窗口内元素的最大值和最小值。思路：经典的单调队列题目，这里采用双端队列处理，维护单调非递增(/减)队列考虑求最小值：若ar[i]小于等于队尾元素，则不断弹出队尾元素，因为ar[i]比它们有更大的发展空间；将ar[i]入队，因为当队首元素不
展开全文
思路 应该是单调队列的板子题吧。我用的是双向队列deque（可能会比较慢）。原理很简单，对于需要输出大的那个数的队列，比较最后的元素是否比新加入的数小，是的话就弹出最后的元素，重复此操作，最终得到一个单调递增的队列。如果队首的元素滑出窗口了，那么直接pop掉，对另外一个队列也是同理。 代码 #inc
展开全文
看了一下所有题解的思路，几乎都是用数据结构完成的，难得一次和所有大佬思路都不一样（且能过），很有必要写篇题解纪念一下。
思路：
滑动窗口，加投票算法：只需要几个变量来记录当前区间中的最值以及最值的数量，即可实现：
情况主要分为
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
