单调队列
239. 滑动窗口最大值
int *maxSlidingWindow(int *nums, int numsSize, int k, int *returnSize) {
*returnSize = numsSize - k + 1;
int *res = (int *) malloc(sizeof(int) * (*returnSize));
// 双端队列,从大到小排,记录在nums中的下标
int dequeue[100001];
int front = 0, rear = 0;
// 先把窗口扩大到k-1
for (int i = 0; i
1438. 绝对差不超过限制的最长连续子数组
int minDeque[100001];
int maxDeque[100001];
int maxFront, maxRear, minFront, minRear;
int *arr;
int max(int a, int b) {
return a > b ? a : b;
}
int min(int a, int b) {
return a > b ? b : a;
}
// 子数组中任意两个元素差值不大于limit转换为最大值和最小值的差值不大于limit
bool ok(int limit, int number) {
// 队列为空,number就作为最大值;否则,比较队列中的记录的当前窗口最大值和number
int MAX = maxFront = arr[r]) minRear--;
minDeque[minRear++] = r;
}
void pop(int l) {
// 滑动窗口移除的刚好是最大元素,则将其从队列中移除
if (maxFront
P2698 [USACO12MAR] Flowerpot S
// 接取落水的最小花盆
// 老板需要你帮忙浇花。给出 N 滴水的坐标,y 表示水滴的高度,x 表示它下落到 x 轴的位置
// 每滴水以每秒1个单位长度的速度下落。你需要把花盆放在 x 轴上的某个位置
// 使得从被花盆接着的第 1 滴水开始,到被花盆接着的最后 1 滴水结束,之间的时间差至少为 D
// 我们认为,只要水滴落到 x 轴上,与花盆的边沿对齐,就认为被接住
// 给出 N 滴水的坐标和 D 的大小,请算出最小的花盆的宽度 W
// 测试链接 : https://www.luogu.com.cn/problem/P2698
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code,提交时请把类名改成"Main",可以直接通过
import java.io.*;
import java.util.Arrays;
class Main {
public static int MAXN = 100005;
public static int[][] arr = new int[MAXN][2];
public static int n, d;
public static int[] maxDeque = new int[MAXN];
public static int[] minDeque = new int[MAXN];
public static int maxh, maxt, minh, mint;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer in = new StreamTokenizer(br);
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
while (in.nextToken() != StreamTokenizer.TT_EOF) {
n = (int) in.nval;
in.nextToken();
d = (int) in.nval;
for (int i = 0; i a[0] - b[0]);
maxh = maxt = minh = mint = 0;
int ans = Integer.MAX_VALUE;
for (int l = 0, r = 0; l =d
public static boolean ok() {
int max = maxh = d;
}
public static void push(int r) {
while (maxh = arr[r][1]) {
mint--;
}
minDeque[mint++] = r;
}
public static void pop(int l) {
if (maxh
862. 和至少为 K 的最短子数组
int min(int a, int b) {
return a > b ? b : a;
}
int shortestSubarray(int *nums, int numsSize, int k) {
int res = 0x7fffffff;
// 单调队列:记录前缀和的下标,前缀和按从小到大排列
int minDeque[100002];
int front = 0, rear = 0;
long long prefixSums[numsSize + 1];
minDeque[rear++] = 0;
prefixSums[0] = 0;
for (int i = 1; i = prefixSums[i])
rear--;
// 前缀和下标入队
minDeque[rear++] = i;
// 窗口左边移出
while (front + 1 = k)
front++;
// 更新符合条件的子数组的最小长度
if (front = k)
res = min(res, i - minDeque[front]);
}
return res == 0x7fffffff ? -1 : res;
}
1499. 满足不等式的最大值
int max(int a, int b) {
return a > b ? a : b;
}
// 所有的点已按照x坐标递增排序
int findMaxValueOfEquation(int **points, int pointsSize, int *pointsColSize, int k) {
int maxDeque[100001][2];
int front = 0, rear = 0;
int res = 0x80000000;
for (int i = 0, x, y; i
2071. 你可以安排的最多任务数目
int *tasks;
int *workers;
int tasksSize;
int workersSize;
int deque[50001];
int front, rear;
int cmp(const void *a, const void *b) {
return *(int *) a - *(int *) b;
}
int min(int a, int b) {
return a > b ? b : a;
}
// tasks[tl....tr]需要力量最小的几个任务
// workers[wl....wr]力量值最大的几个工人
// 返回在药的数量不超情况下,任务是否全部都能完成
bool f(int tl, int tr, int wl, int wr, int strength, int pills) {
front = 0;
rear = 0;
// 已使用的药的数量
int count = 0;
// i为工人编号,j为任务编号
for (int i = wl, j = tl; i
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net