首页 > 其他分享 >单调队列

单调队列

时间:2024-09-05 20:13:40浏览次数:12  
标签:right min 队列 int front include 单调 dq

单调队列

  • 经典用法:维持滑动窗口滑动过程中的最大值或最小值。最大值时,单调队列从头到尾降序
  • 维持求解答案的可能性
    1. 单调队列里所有对象按照规定好的单调性组织
    2. 当某个对象从队尾进入单调队列时,会从队头或者队尾依次淘汰单调队列里,对后续求解答案没有帮助的对象
    3. 每个对象一旦弹出,可以结算其参与的答案,随后这个对象不再参与后续求解

239. 滑动窗口最大值

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int> &nums, int k) {
        vector<int> res;
        // 单调队列,队头到队尾递减,存的是下标
        deque<int> dq;

        // 先构造出长度 k 的窗口,并记录这个窗口的最大值
        for (int right = 0; right < k; ++right) {
            // 从队尾依次弹出小于等于的
            while (!dq.empty() && nums[dq.back()] <= nums[right])
                dq.pop_back();
            dq.emplace_back(right);
        }
        res.emplace_back(nums[dq.front()]);

        // 窗口:[left, right]
        for (int right = k, left = 1; right < nums.size(); ++right, left++) {
            // 从队尾依次弹出小于等于的
            while (!dq.empty() && nums[dq.back()] <= nums[right])
                dq.pop_back();
            // 从队头依次弹出出界的
            while (!dq.empty() && dq.front() < left)
                dq.pop_front();

            dq.emplace_back(right);
            res.emplace_back(nums[dq.front()]);
        }
        return res;
    }
};

1438. 绝对差不超过限制的最长连续子数组

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

class Solution {
public:

    bool withinLimit(vector<int> &nums, deque<int> &max_dq, deque<int> &min_dq, int number, int limit) {
        int maxVal = max_dq.empty() ? number : max(number, nums[max_dq.front()]);
        int minVal = min_dq.empty() ? number : min(number, nums[min_dq.front()]);
        return maxVal - minVal <= limit;
    }

    int longestSubarray(vector<int> &nums, int limit) {
        int res;
        int len = nums.size();
        deque<int> max_dq;
        deque<int> min_dq;

        for (int left = 0, right = 0; left < len; left++) {
            // 窗口:[left, right),不超过限制才能加入窗口
            while (right < len && withinLimit(nums, max_dq, min_dq, nums[right], limit)) {
                // 加入单调队列
                while (!max_dq.empty() && nums[max_dq.back()] <= nums[right])
                    max_dq.pop_back();
                while (!min_dq.empty() && nums[min_dq.back()] >= nums[right])
                    min_dq.pop_back();
                max_dq.emplace_back(right);
                min_dq.emplace_back(right);
                right++;
            }

            // 退出循环时,[left, right),就是从 left 右扩的最长子数组
            res = max(res, right - left);

            // 考虑下个左边界 left + 1 开始的窗口时,先移除将会越界的
            if (max_dq.front() == left) max_dq.pop_front();
            if (min_dq.front() == left) min_dq.pop_front();
        }
        return res;
    }
};

接取落水的最小花盆

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

bool cmp(pair<int, int> p1, pair<int, int> p2) {
    return p1.first < p2.first;
}

bool ok(vector<pair<int, int>> &arr, deque<int> &maxDeque, deque<int> &minDeque, int limit) {
    int maxVal = maxDeque.empty() ? 0 : arr[maxDeque.front()].second;
    int minVal = minDeque.empty() ? 0 : arr[minDeque.front()].second;
    return maxVal - minVal >= limit;
}

int main() {
    // 录入数据
    int len, limit;
    cin >> len >> limit;
    vector<pair<int, int>> arr;
    for (int i = 0, index, val; i < len; ++i) {
        cin >> index >> val;
        arr.emplace_back(make_pair(index, val));
    }
    // 按下标升序排序
    sort(begin(arr), end(arr), cmp);

    deque<int> maxDeque;
    deque<int> minDeque;
    int res = 0x7fffffff;

    for (int left = 0, right = 0; left < len; ++left) {
        while (right < len && !ok(arr, maxDeque, minDeque, limit)) {
            while (!maxDeque.empty() && arr[maxDeque.back()].second <= arr[right].second)
                maxDeque.pop_back();
            while (!minDeque.empty() && arr[minDeque.back()].second >= arr[right].second)
                minDeque.pop_back();
            maxDeque.emplace_back(right);
            minDeque.emplace_back(right);
            right++;
        }
        if (ok(arr, maxDeque, minDeque, limit))
            res = min(res, arr[right - 1].first - arr[left].first);

        if (!maxDeque.empty() && maxDeque.front() == left) maxDeque.pop_front();
        if (!minDeque.empty() && minDeque.front() == left) minDeque.pop_front();
    }
    res = res == 0x7fffffff ? -1 : res;
    cout << res;
}

862. 和至少为 K 的最短子数组

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

class Solution {
public:
    int shortestSubarray(vector<int> &nums, int k) {
        int len = nums.size() + 1;
        // sum[i] 表示前 i 个数的前缀和
        vector<long> sum(len, 0);
        for (int i = 1; i < len; ++i)
            sum[i] = sum[i - 1] + nums[i - 1];

        // 递增的单调队列
        deque<int> min_dq;
        int res = INT_MAX;
        // 处理前 i 个数的前缀和,判断以 i 结尾,min_dq.front() 开头的一段子数组累加和是否达标
        for (int i = 0; i < len; ++i) {
            while (!min_dq.empty() && sum[i] - sum[min_dq.front()] >= k) {
                // 达标就更新结果,然后把滑动窗口的左边界右移
                res = min(res, i - min_dq.front());
                min_dq.pop_front();
            }
            // 前 i 个数的前缀和加入单调队列
            // 先弹出违背递增的元素
            while (!min_dq.empty() && sum[min_dq.back()] >= sum[i])
                min_dq.pop_back();
            // 再加入
            min_dq.emplace_back(i);
        }
        return res == INT_MAX ? -1 : res;
    }
};

1499. 满足不等式的最大值

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

class Solution {
public:
    // 横坐标递增,求在 x[j] - x[i] <= k 的条件下,x[j] - x[i] + y[i] + y[j] 的最大值
    int findMaxValueOfEquation(vector<vector<int>> &points, int k) {
        // 单调递减队列排序依据是 x[j] - x[i],存的是坐标
        deque<pair<int, int>> maxDq;
        int len = points.size();
        int res = INT_MIN;

        for (int i = 0, x, y; i < len; ++i) {
            x = points[i][0];
            y = points[i][1];
            // x 的距离超过 k
            while (!maxDq.empty() && (x - maxDq.front().first > k))
                maxDq.pop_front();
            if (!maxDq.empty())
                res = max(res, maxDq.front().second + y + x - maxDq.front().first);
            // 入队,淘汰违背递减的元素
            while (!maxDq.empty() && maxDq.back().second - maxDq.back().first <= y - x)
                maxDq.pop_back();
            maxDq.emplace_back(make_pair(x, y));
        }
        return res;
    }
};

2071. 你可以安排的最多任务数目

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

class Solution {
public:
    bool judge(vector<int> &tasks, vector<int> &workers, int pills, int strength,
               int tl, int tr, int wl, int wr) {
        deque<int> minDq;
        // 已经使用的药量
        int cost = 0;
        // i 为工人编号,j 为任务编号
        for (int i = wl, j = tl; i <= wr; ++i) {
            // 当前工人初始能力能完成的任务全都入队
            while (j <= tr && tasks[j] <= workers[i]) {
                minDq.emplace_back(j);
                j++;
            }
            if (!minDq.empty() && tasks[minDq.front()] <= workers[i]) {
                // 没吃药时从队列里选任务量最少的任务完成
                minDq.pop_front();
            } else {
                // 完成不了,就吃药,并且把吃药后能完成的任务全都入队
                while (j <= tr && tasks[j] <= workers[i] + strength) {
                    minDq.emplace_back(j);
                    j++;
                }
                if (minDq.empty()) {
                    // 吃了药都做不了一个任务,那这些任务必定不能全部完成
                    // 因为有人啥也干不了,而任务和人数又是一样的
                    return false;
                } else {
                    // 吃了药就选队列里选任务量最多的任务完成,充分利用药的加成
                    // 因为后面的人可能吃不到药,完成不了那么多任务量的任务
                    minDq.pop_back();
                    // 消耗一个药丸
                    cost++;
                }
            }
        }
        // 是否超出药丸总数
        return cost <= pills;
    }

    int maxTaskAssign(vector<int> &tasks, vector<int> &workers, int pills, int strength) {
        sort(begin(tasks), end(tasks));
        sort(begin(workers), end(workers));
        int tLen = tasks.size();
        int wLen = workers.size();
        
        int left = 0;
        int right = min(tLen, wLen);
        int mid;
        
        // 右边界
        while (left <= right) {
            // 人数等于工作数等于 mid
            mid = left + ((right - left) >> 1);
            // 最少工作量的一组工作,交给工作能力最强的一群工人
            if (judge(tasks, workers, pills, strength,
                      0, mid - 1, wLen - mid, wLen - 1))
                left = mid + 1;
            else
                right = mid - 1;
        }
        return right;
    }
};

标签:right,min,队列,int,front,include,单调,dq
From: https://www.cnblogs.com/sprinining/p/18399183

相关文章

  • C++ STL queue容器——队列
    queue容器基本概念queue是一种**先进先出的数据结构,它有两个出口,queue容器允许从一端新增元素,从另一端移除元素。queue容器没有迭代器,所有元素进出都必须符合“先进先出”条件,只有顶端的元素才有机会被外界取用,所以也不提供遍历功能。queue容器常用操作构造函数queue<T>qu......
  • 一个故事理解消息队列-下
    这是一篇迟到一月有余的文章。在7月18号,我用了一个故事作为案例,介绍了消息队列的基本功能和应用场景。本打算第二天介绍消息队列的主要功能特性的,由于文章排期等其他因素影响,故更新搁置了。这篇文章,接上篇《一个故事理解消息队列-上》,以Kafka为例,为大家介绍消息队列的主要功能......
  • promise实现一个动态删减并持续执行的队列
     promiseQueue.js:/**@Author:Simoon.jia*@Date:2024-09-0416:00:24*@LastEditors:Simoon.jia*@LastEditTime:2024-09-0416:55:48*@Description:描述*/exportclassPromiseQueue{constructor(){this.queue=[];this.isProcessing=......
  • 【大数据】Kafka与RocketMQ:消息队列界的“绝代双骄”
    文章目录一、开场白:消息队列江湖的“风云际会”二、正文1.Kafka与RocketMQ的由来:两颗璀璨的明星2.发展历程:各自的成长轨迹3.区别:各有千秋,各领风骚4.使用场景:谁的主场,谁的地盘?5.如何选择:挑花了眼怎么办?6.市场占用情况:谁更受欢迎?三、结尾:携手共创,消息队列的未来......
  • Lcode算法26:队列实现栈
    请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。实现 MyStack 类:voidpush(intx) 将元素x压入栈顶。intpop() 移除并返回栈顶元素。inttop() 返回栈顶元素。booleanempty() 如果栈是空的,返回 true ;否则,返回......
  • [Python手撕]用队列实现栈/用栈实现队列
    用队列实现栈classMyStack:def__init__(self):self.length=0self.queue1=[]self.queue2=[]defpush(self,x:int)->None:self.queue1.append(x)self.length+=1defpop(self)->int:......
  • CSP-J初赛知识点总复习( 3.3链式栈 3.4链式队列3.5链表习题)
    链式栈:(代码)#include<bits/stdc++.h>usingnamespacestd;//栈元素structStack{intdata;structStack*next;};Stack*top=NULL;//栈顶指针//入栈voidpush(intx){Stack*p=newStack;p->data=x;p->next=top;top=p;//修......
  • 进程间通信——消息队列(通俗易懂)
    消息队列概念消息队列是消息的链表,存放在内核中并由消息队列标识符标识,消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺陷。消息队列包括POSIX消息队列和SystemV消息队列。消息队列是UNIX下不同进程之间实现共享资源的一种机制,UNIX......
  • 进程间通信(信号灯集、消息队列)
    1.信号灯集线程:全局变量,同步通过信号量初始化:sem_init(&sem,0,0);申请资源:sem_wait(&sem);P操作,-1释放资源:sem_post(&sem);V操作,+11.1特点信号灯(semaphore),也叫信号量,信号灯集是一个信号灯的集合。它是不同进程间或一个给定进程内部不同线程间同步的机制;而Posi......
  • 第十章 单调栈 Part2
    目录任务42.接雨水思路84.柱状图中最大的矩形思路任务42.接雨水给定n个非负整数表示每个宽度为1的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。思路按照横向计算,单调栈的思路得到left和right,然后得到h和w,最终累加结果。classSolution:deftrap(se......