題目來源：最大子矩陣 - 藍(lán)橋云課 (lanqiao.cn)
問題描述
小明有一個大小為 N×M?的矩陣, 可以理解為一個?N?行?M?列的二維數(shù)組。
我們定義一個矩陣?m?的穩(wěn)定度?f(m)?為f(m)=max(m)?min(m), 其中 max(m)?表示矩陣?m?中的最大值,?min(m)?表示矩陣?m?中的最小值。
現(xiàn)在小明想要從這個矩陣中找到一個穩(wěn)定度不大于 limit 的子矩陣, 同時他還希望這個子矩陣的面積越大越好 (面積可以理解為矩陣中元素個數(shù))。
子矩陣定義如下: 從原矩陣中選擇一組連續(xù)的行和一組連續(xù)的列, 這些行列交點(diǎn)上的元素組成的矩陣即為一個子矩陣。
輸入格式
第一行輸入兩個整數(shù)?N,M, 表示矩陣的大小。
接下來?N?行, 侮行輸入?M?個整數(shù)，表示這個矩陣。
最后一行輸入一個整數(shù) limit, 表示限制。
輜出格式
輸出一個整數(shù). 分別表示小明選擇的子矩陣的最大面積。
樣例輸入
3 4 2 0 7 9 0 6 9 7 8 4 6 4 8樣例輸出
6樣例說明
滿足穩(wěn)定度不大于 8 的且面積最大的子矩陣總共有三個, 他們的面積都是 6 (粗體表示子矩陣元素)
2?0 7 9
0 6?9 7
8 4?6 4? ? ? ? ? ? ?
2 0?7 9
0 6?9 7
8 4?6 4
2 0 7 9
0?6 9 7
8?4 6 4
評測用例規(guī)模與約定
對于所有評測用例,?0≤0≤?矩陣元素值, limit?≤105≤105?。
題目大意
給定一個N*M的二維矩陣和一個數(shù)字limlit，求出符合穩(wěn)定度f(m)<=limit的面積最大的子矩陣。
f(m)為當(dāng)前子矩陣的最大值-最小值
解法一：暴力法（通過30%）
????????通過四重循環(huán)（四條邊）枚舉每個子矩陣，然后再計算當(dāng)前子矩陣的最大值和最小值之差，若差值滿足<=limit，則維護(hù)更新面積最大值。
算法復(fù)雜度大于O(n^4）
解法二：?尺取法+單調(diào)隊列（通過100%）
解題關(guān)鍵（三問）：
1、如何較為快速地確定當(dāng)前子矩陣的大?。?/h4>
雙指針?biāo)惴?尺取法)
【圖解】尺取法?
1、一開始左右指針都是從左端點(diǎn)開始?
?
?2、右指針先向右移動
?
3、右指針移動到剛好滿足f(m)<=limit?的臨界位置
?
4、右指針再向右移動，這時候在區(qū)間[l, r']就不滿足?f(m)<=limit?
?
5、此時開始移動左指針?
?
6、當(dāng)左指針移動到剛好滿足f(m)<=limit?的臨界位置時，右指針開始移動，這樣周而復(fù)始，直到右指針達(dá)到終點(diǎn)。
?
?文章來源地址http://www.zghlxwxcb.cn/news/detail-415617.html
????????觀察數(shù)據(jù)，可發(fā)現(xiàn)行的數(shù)據(jù)范圍較小，列的數(shù)據(jù)范圍較大，因此子矩陣的上下邊可以通二.重遍歷確定，復(fù)雜度，子矩陣的左右邊采用雙指針?biāo)惴ㄟM(jìn)行確定，復(fù)雜度。
算法復(fù)雜度
??
2、如何較為快速地找出當(dāng)前子矩陣的兩個最值?
????????每次移動左右指針，都會后一整列的數(shù)字進(jìn)入或退出當(dāng)前子矩陣，我們需要先計算出當(dāng)前列[up,down]范圍的最值。優(yōu)化：通過轉(zhuǎn)置矩陣，我們可以利用切片的方式，不用循環(huán)求出原矩陣每一列[up,down]范圍內(nèi)的最值
??
3、當(dāng)前子矩陣實(shí)在不斷移動的，如何在移動過程中維護(hù)最值?
????????使用兩個隊列分別記錄當(dāng)前子矩陣的最大值和最小值，維護(hù)隊列的單調(diào)性，雙指針移動過程中時刻更新隊列。
單調(diào)隊列
維護(hù)最大值的單調(diào)隊列示例：
? ? ? ? ?第一個數(shù)字直接加入隊列，后面每一列如果出現(xiàn)的數(shù)字比隊列最后一個元素小，則加入隊列，否則去掉隊列最后一個元素，?再與隊列最后一個比較，直到隊列為空或者該數(shù)字比隊列最后一個元素小再將該數(shù)字加入隊列。
?文章來源：http://www.zghlxwxcb.cn/news/detail-415617.html
維護(hù)最大值的單調(diào)隊列，內(nèi)部元素是遞減排列的
維護(hù)最小值的單調(diào)隊列，內(nèi)部元素是遞增排列的
解題思路：雙指針+單調(diào)隊列
1、二重循環(huán)對矩陣的上下邊界進(jìn)行遍歷
2、對于每個確定的上下邊界up,down，左右邊界采用雙指針?biāo)惴ù_定
3、使用兩個隊列分別記錄當(dāng)前子矩陣的最大值和最小值，維護(hù)隊列的單調(diào)性，雙指針移動過程中時刻更新隊列
4、初始res=0保存結(jié)果，雙指針移動過程中維護(hù)最大值
代碼演示
from collections import deque
n, m = map(int, input().split())
mat = [list(map(int, input().split())) for _ in range(n)] # 二維列表存矩陣：n行m列
lim = int(input())
max_res = 0
# 轉(zhuǎn)置矩陣 m行n列
remat = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
remat[i][j] = mat[j][i]
for up in range(n): # 兩個for循環(huán)遍歷上下邊
for down in range(up, n):
l = 0 # 左指針初始化
maxq = deque() # 最大值的單調(diào)隊列
minq = deque() # 最小值的單調(diào)隊列
#maxq.append(max(remat[l][up: down + 1]))
#minq.append(min(remat[l][up: down + 1]))
for r in range(0, m):
newmax = max(remat[r][up: down + 1]) # 右邊新的一列l(wèi)：[up,down]最大值
while len(maxq) and maxq[-1] < newmax:# 最大值的單調(diào)隊列的最后一個比新的最大值小
maxq.pop() # 刪除隊列最后一個
maxq.append(newmax) # 把新的一列的最大值放入隊列
newmin = min(remat[r][up: down + 1])
while len(minq) and minq[-1] > newmin:
minq.pop()
minq.append(newmin)
cumax, cumin = maxq[0], minq[0] # 子矩陣的最大值和最小值
while cumax - cumin > lim and l < r: # 最大-最小＞lim，左指針＜右指針
if len(maxq) and max(remat[l][up: down + 1]) == maxq[0]: # 最左邊的一列的最大值是子矩陣的最大值
maxq.popleft() # 刪除最大值，因?yàn)樽笾羔樢蛴乙苿? if len(minq) and min(remat[l][up: down + 1]) == minq[0]:
minq.popleft()
cumax, cumin = maxq[0], minq[0] # 更新子矩陣的最大值和最小值
l += 1 # 左指針要向右移動
if cumax - cumin > lim: # 特判：如果l=r且最大-最?。緇im
continue
cu_square = (r - l + 1) * (down - up + 1) # 計算面積
max_res = max(max_res, cu_square)
print(max_res)?
?
?
?
?
到了這里，關(guān)于藍(lán)橋杯刷題016——最大子矩陣（尺取法+單調(diào)隊列）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
