2020-02-13 單調(diào)隊(duì)列

模板:遞增隊(duì)列或是遞減隊(duì)列只需要修改刪除隊(duì)尾元素的判斷條件即可洞翩。
原理 以遞增隊(duì)列舉例:
以一個(gè)長(zhǎng)度為k的移動(dòng)窗口從k處開(kāi)始移動(dòng)座舍,遍歷數(shù)組中的每個(gè)元素沮翔,添加到隊(duì)列末尾并且于前一個(gè)元素相比較,直到有一個(gè)元素大于當(dāng)前元素曲秉,退出循環(huán)采蚀,將當(dāng)前元素加入隊(duì)列,并且將位置坐標(biāo)另記入一個(gè)位置數(shù)組承二。尋找k長(zhǎng)度窗口內(nèi)的最大值則只需要在位置數(shù)組遍歷榆鼠,第一個(gè)大于等于i的就是所求的最大值。
···

include<iostream>

include<cstdio>

include<cstring>

include<string>

include<queue>

include<map>

include<vector>

include<algorithm>

include<stack>

include<set>

using namespace std;
typedef long long ll;
const int N=1000010;
const int inf=0x3f3f3f;
int n,k;
int q[N],mk[N],a[N];
void qmax()
{
int i,st=1,tt=1;
for(i=1;i<=n;i++)
{
while(tt<st&&q[st-1]<=a[i]) st--;
q[st]=a[i];mk[st]=i;st++;
if(i>=k)
{
while(tt<st&&mk[tt]<=i-k) tt++;
printf("%d ",q[tt]);
}
}
}
void qmin()
{
int i,st=1,tt=1;
for(i=1;i<=n;i++)
{
while(tt<st&&q[st-1]>=a[i]) st--;
q[st]=a[i];mk[st]=i;st++;
if(i>=k)
{
while(tt<st&&mk[tt]<=i-k) tt++;
printf("%d ",q[tt]);
}
}
}
int main() {
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
qmin();
printf("\n");
qmax();
printf("\n");
return 0;
}···

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末亥鸠,一起剝皮案震驚了整個(gè)濱河市妆够,隨后出現(xiàn)的幾起案子识啦,更是在濱河造成了極大的恐慌,老刑警劉巖神妹,帶你破解...
    沈念sama閱讀 212,816評(píng)論 6 492
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件颓哮,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡鸵荠,警方通過(guò)查閱死者的電腦和手機(jī)题翻,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,729評(píng)論 3 385
  • 文/潘曉璐 我一進(jìn)店門(mén),熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)腰鬼,“玉大人嵌赠,你說(shuō)我怎么就攤上這事∠ㄉ模” “怎么了姜挺?”我有些...
    開(kāi)封第一講書(shū)人閱讀 158,300評(píng)論 0 348
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)彼硫。 經(jīng)常有香客問(wèn)我炊豪,道長(zhǎng),這世上最難降的妖魔是什么拧篮? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 56,780評(píng)論 1 285
  • 正文 為了忘掉前任词渤,我火速辦了婚禮,結(jié)果婚禮上串绩,老公的妹妹穿的比我還像新娘缺虐。我一直安慰自己,他們只是感情好礁凡,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,890評(píng)論 6 385
  • 文/花漫 我一把揭開(kāi)白布高氮。 她就那樣靜靜地躺著,像睡著了一般顷牌。 火紅的嫁衣襯著肌膚如雪剪芍。 梳的紋絲不亂的頭發(fā)上,一...
    開(kāi)封第一講書(shū)人閱讀 50,084評(píng)論 1 291
  • 那天窟蓝,我揣著相機(jī)與錄音罪裹,去河邊找鬼。 笑死运挫,一個(gè)胖子當(dāng)著我的面吹牛状共,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播滑臊,決...
    沈念sama閱讀 39,151評(píng)論 3 410
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼口芍,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼箍铲!你這毒婦竟也來(lái)了雇卷?” 一聲冷哼從身側(cè)響起,我...
    開(kāi)封第一講書(shū)人閱讀 37,912評(píng)論 0 268
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎关划,沒(méi)想到半個(gè)月后小染,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 44,355評(píng)論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡贮折,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,666評(píng)論 2 327
  • 正文 我和宋清朗相戀三年裤翩,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片调榄。...
    茶點(diǎn)故事閱讀 38,809評(píng)論 1 341
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡踊赠,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出每庆,到底是詐尸還是另有隱情筐带,我是刑警寧澤,帶...
    沈念sama閱讀 34,504評(píng)論 4 334
  • 正文 年R本政府宣布缤灵,位于F島的核電站伦籍,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏腮出。R本人自食惡果不足惜帖鸦,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 40,150評(píng)論 3 317
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望胚嘲。 院中可真熱鬧作儿,春花似錦、人聲如沸馋劈。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 30,882評(píng)論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)侣滩。三九已至口注,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間君珠,已是汗流浹背寝志。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 32,121評(píng)論 1 267
  • 我被黑心中介騙來(lái)泰國(guó)打工, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留策添,地道東北人材部。 一個(gè)月前我還...
    沈念sama閱讀 46,628評(píng)論 2 362
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像唯竹,于是被迫代替她去往敵國(guó)和親乐导。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,724評(píng)論 2 351

推薦閱讀更多精彩內(nèi)容

  • 在C語(yǔ)言中,五種基本數(shù)據(jù)類(lèi)型存儲(chǔ)空間長(zhǎng)度的排列順序是: A)char B)char=int<=float C)ch...
    夏天再來(lái)閱讀 3,339評(píng)論 0 2
  • 題目來(lái)源:1浸颓、中興物臂、華為旺拉、慧通、英華達(dá)棵磷、微軟亞洲技術(shù)中心等中外企業(yè)面試題目蛾狗;2、C 語(yǔ)言面試寶典(林銳《高質(zhì)量編程...
    月震閱讀 1,804評(píng)論 0 1
  • C語(yǔ)言的學(xué)習(xí)要從基礎(chǔ)開(kāi)始仪媒,這里是100個(gè)經(jīng)典的算法-1C語(yǔ)言的學(xué)習(xí)要從基礎(chǔ)開(kāi)始沉桌,這里是100個(gè)經(jīng)典的 算法 題目:...
    Poison_19ce閱讀 1,129評(píng)論 0 0
  • 計(jì)算機(jī)二級(jí)C語(yǔ)言上機(jī)題庫(kù)(南開(kāi)版) 1.m個(gè)人的成績(jī)存放在score數(shù)組中,請(qǐng)編寫(xiě)函數(shù)fun,它的功能是:將低于平...
    MrSunbeam閱讀 6,336評(píng)論 1 42
  • "use strict";function _classCallCheck(e,t){if(!(e instanc...
    久些閱讀 2,028評(píng)論 0 2