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

单调队列

时间:2024-03-15 16:56:09浏览次数:30  
标签:mm 队列 back pop int vector front 单调

题目1

点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
signed main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n,m;cin>>n>>m;
    int nn,mm;cin>>nn>>mm;
    vector<vector<int>>t(n+1,vector<int>(m+1,0));
    vector<vector<int>>sum(n+1,vector<int>(m+1,0));
    vector<vector<int>>qmax(n+1,vector<int>(m+1,0)),qqmax(n+1,vector<int>(m+1,0));
    vector<vector<int>>qmin(n+1,vector<int>(m+1,inf)),qqmin(n+1,vector<int>(m+1,inf));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>t[i][j];
    for(int i=1;i<=n;i++)
    {
        //存储编号
        deque<int>q;
        for(int j=1;j<=m;j++)
        {
            if(!q.empty()&&j-q.front()>=mm) q.pop_front();
            while(!q.empty()&&t[i][q.back()]<t[i][j]) q.pop_back();
            q.push_back(j);
            if(j>=mm) qmax[i][j]=t[i][q.front()]; 
        }
        q.clear();
        for(int j=1;j<=m;j++)
        {
            if(!q.empty()&&j-q.front()>=mm) q.pop_front();
            while(!q.empty()&&t[i][q.back()]>t[i][j]) q.pop_back();
            q.push_back(j);
            if(j>=mm) qmin[i][j]=t[i][q.front()]; 
        }
    }

    for(int j=mm;j<=m;j++)
    {
        deque<int>q;
        for(int i=1;i<=n;i++)
        {
            if(!q.empty()&&i-q.front()>=nn) q.pop_front();
            while(!q.empty()&&qmax[q.back()][j]<qmax[i][j]) q.pop_back();
            q.push_back(i);
            if(i>=nn) qqmax[i][j]=qmax[q.front()][j]; 
        }
        q.clear();
        for(int i=1;i<=n;i++)
        {
            if(!q.empty()&&i-q.front()>=nn) q.pop_front();
            while(!q.empty()&&qmin[q.back()][j]>qmin[i][j]) q.pop_back();
            q.push_back(i);
            if(i>=nn) qqmin[i][j]=qmin[q.front()][j]; 
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+t[i][j];
        }
    }
    int ans=0;
    for(int i=nn;i<=n;i++)
    {
        for(int j=mm;j<=m;j++)
        {
            int s=sum[i][j]-sum[i-nn][j]-sum[i][j-mm]+sum[i-nn][j-mm];
            ans=max(ans,s*(qqmax[i][j]-qqmin[i][j]));
        }
    }
    cout<<ans<<"\n";
    return 0;
}

标签:mm,队列,back,pop,int,vector,front,单调
From: https://www.cnblogs.com/mhw-mathcode/p/18075806

相关文章

  • leedcode-用队列实现栈
    利用内置的listclassMyStack:def__init__(self):#初始化一个空列表用于存储栈的元素self.li=list()defpush(self,x:int)->None:#向栈中压入元素xself.li.append(x)defpop(self)->int:#从栈顶弹......
  • 代码随想录算法训练营第十天| 232. 用栈实现队列 225. 用队列实现栈
    232.用栈实现队列https://leetcode.cn/problems/implement-queue-using-stacks/description/classMyQueue{Stack<Integer>stackIn;Stack<Integer>stackOut;publicMyQueue(){stackIn=newStack<>();stackOut=new......
  • 单调栈C++
    一、每日温度  1、题目:请根据每日气温列表,重新生成一个列表。对应位置的输出为:要想观测到更高的气温,至少需要等待的天数。如果气温在这之后都不会升高,请在该位置用0来代替。例如,给定一个列表temperatures=[73,74,75,71,69,72,76,73],你的输出应该是[1,1,......
  • Python使用RocketMQ(消息队列)
    消息队列在日常开发中比较常用的开发中间件,每家大厂一般都会具有自己的消息队列服务器。本文主要讲述Python中如何使用RocketMQ的相关SDK。希望大家在阅读本文前可以先了解一下RocketMQ的基本知识。使用 pipinstallrocketmq-ihttps://pypi.tuna.tsinghua.edu.cn/sim......
  • LeetCode232.栈实现队列
    ques:用两个栈实现队列功能ans:与225一样的思路,看完225大佬们的题解之后能很轻松的想出思路,用s1来实现真正模拟队列中的元素顺序,借助s2辅助完成这一排序代码实现#include<iostream>#include<stack>usingnamespacestd;classMyQueue{private:stack<int>s1;/......
  • 多线程(代码案例: 单例模式, 阻塞队列, 生产者消费者模型,定时器)
    设计模式是什么类似于棋谱一样的东西计算机圈子里的大佬为了能让小菜鸡的代码不要写的太差针对一些典型的场景,给出了一些典型的解决方案这样小菜鸡们可以根据这些方案(ACM里面叫板子,象棋五子棋里叫棋谱,咱这里叫设计模式),略加修改,这样代码再差也差不到哪里去......
  • JS 队列(数据结构)- 笔记
    【队列】代码:/***链表队列*/classLinkedListQueue{/**@type{ListNode}*/#head;/**@type{ListNode}*/#tail;/**@type{number}*/#size;constructor(){this.#head=null;this.#tail=null;this......
  • LeetCode225.队列实现栈
    ques:用两个队列模拟栈(我用的是一个)ans:用的C++标准库里面的Queue模板类创建实例,主要思路就是push函数里面做文章,其余函数pop/top/empty都正常实现。根据栈和队列的特性,插入点不变,只能是队尾,但每次插入队尾总想把他放在栈顶,所以就让队列前面的元素依次出队并排在队尾,即可......
  • FreeRTOS教程4 消息队列
    1、准备材料正点原子stm32f407探索者开发板V2.4STM32CubeMX软件(Version6.10.0)KeilµVision5IDE(MDK-Arm)野火DAP仿真器XCOMV2.6串口助手2、学习目标本文主要学习FreeRTOS消息队列的相关知识,包括消息队列概述、创建删除复位队列、写入/读取数据到队列等关于队列的基础知......
  • 【OJ】猫狗队列
    猫狗队列思路用两个队列分别保存猫、狗,用各个的入队计数判断任一出队时选择哪一种,指定类别出队则直接从相应队列出队。实现Python输入测试testCatDogQ.txt65adddog29addcat9adddog40adddog38addcat32adddog20addcat45pollAlladdcat37isDogEm......