發(fā)個(gè)昨天考試的題 二維單調(diào)隊(duì)列 單調(diào)隊(duì)列之前也學(xué)了但沒(méi)做過(guò)題，沒(méi)寫(xiě)過(guò)。但我感覺(jué)也不難，今天直接搞了個(gè)二維的； 發(fā)個(gè)一維的講解，不會(huì)的先看一下，以便看懂下面的題解。點(diǎn)這里 T1 為了和諧 (square.pas/c/cpp) [問(wèn)題背景] 在機(jī)房里，有兩只小可愛(ài)，一只大可愛(ài)，一只小可愛(ài)。其中大可 愛(ài)對(duì)大的東西感興趣，小可愛(ài)對(duì)小的東西感興趣。 現(xiàn)在有一個(gè) a*b 的矩陣，矩陣中每個(gè)位置都有一個(gè)非負(fù)整數(shù) i （ 0<=i<=2000 000 000），兩只小可愛(ài)要在這個(gè)矩陣中選擇一個(gè) n*n 的 正方形，大可愛(ài)要正方形中的最大數(shù)，小可愛(ài)要正方形中的最小數(shù)。 但是，如果兩個(gè)人的數(shù)字差距過(guò)大的話，就會(huì)造成矛盾……為了 機(jī)房人民的和諧相處，請(qǐng)你幫他們選擇這個(gè)正方形，使得這個(gè)差距最 小。 [問(wèn)題描述] 有一個(gè) a*b 的整數(shù)組成的矩陣，現(xiàn)請(qǐng)你從中找出一個(gè) n*n 的正 方形區(qū)域，使得該區(qū)域所有數(shù)中的最大值和最小值的差最小。 INPUT (square.in) 第一行 3 個(gè)整數(shù) a b n 接下來(lái) a 行，每行 b 個(gè)非負(fù)整數(shù)。 OUTPUT (square.out) 僅一個(gè)整數(shù)，表示正方形中最大數(shù)與最小數(shù)之差[樣例輸入] 5 4 2 1 2 5 6 0 17 16 0 16 17 2 1 2 10 2 1 1 2 2 2 [樣例輸出] 1 HINT 1， 矩陣中所有數(shù)小于 2000 000 000 2， 20%數(shù)據(jù)， 2<=a,b<=100, n<=a, n<=b, n<=10 3， 100%數(shù)據(jù)， 2<=a,b<=1000, n<=a, n<=b, n<=100

先每行搞單調(diào)隊(duì)列，一個(gè)最大一個(gè)最小。然后對(duì)應(yīng)存起來(lái)這個(gè)位置區(qū)間的最值。再按列搞，搞出來(lái)就是矩陣的最值。 代碼