傳送門:https://nanti.jisuanke.com/t/42391
題目大意：給你兩個 n * m 的二維排列（1 ~ n * m）像捶。問你最大重合公共子矩陣底靠。
題目思路：
這種問極大子矩陣的題目有兩種方法求解：單調(diào)棧 / 懸線法
方法一：單調(diào)棧
1.關(guān)鍵：
求出每個點最遠(yuǎn)往上衍生多遠(yuǎn)的距離記為val.對于每一行谒臼，相當(dāng)于求解以這一行為底邊的最大柱狀圖面積舒萎。
2.思路：
對于每個點笼痹，正反跑一遍單調(diào)棧坞靶。求出往左最遠(yuǎn)能碰到的距離，往右最遠(yuǎn)能碰到的距離蹂安。(注意轉(zhuǎn)移的時候左邊界是如何衍生的,類似dp)
3.注意點:
這里需要注意連通性：單調(diào)棧中不僅每一列高度是遞增的椭迎，而且要是在原矩陣中列也是兩兩相鄰的。所以當(dāng)新增一列時需判斷連通性田盈。若不連通畜号，需要將棧清空再放入新的列.
方法二：懸線法(dp)? --??核心思想和 [方法一] 大同小異.
1.懸線：
對于每個點，他往上最多能走多少的線叫懸線允瞧。
2.原理:
極大矩陣的上邊界一定被某個障礙物限制著(否則答案可以更大)简软。那么假設(shè)這個障礙物在第i列蛮拔。那么第i列的極大矩陣的底邊那個點到障礙物就是一條懸線.
3.1 答案求解
求解出每個點的1.懸線長，2.以該點為底痹升，以懸線為高往左能夠衍生多長建炫，往右能衍生多長。答案面積就直接計算了疼蛾。
①懸線長height數(shù)組：對于每個點(i,j)踱卵，按(i - 1 , j)點轉(zhuǎn)移即可。
②左右衍生長度left ,right數(shù)組：
第一遍：按(i - 1 , j)/(i , j - 1)點轉(zhuǎn)移即可据过。
第二遍：對于那些height > 1 的點(i , j)，它還需要考慮點(i - 1, j) 的? left 和 right 數(shù)組 對本行的限制妒挎。
3.2 過程要點
注意到：left,right數(shù)組再進行第一遍第二遍dp的時候概念是發(fā)生變化的绳锅。
第一遍時：left,right數(shù)組單純代表每個點往左/右邊最多能衍生多少
第二遍時：left,right數(shù)組代表以該點懸線為高往左/右邊最多能夠衍生多少
所以一定要先讓所有點左右衍生到盡頭，再考慮上一行對本行的限制.(也就是按順序來)
因為根據(jù)dp的含義: left數(shù)組只受左邊第一個障礙物酝掩，還有上一層的left的影響鳞芙。
如果left[i][j - 1] 提前算完兩步了。它的含義也變了期虾。那么在left[i][j]轉(zhuǎn)移的時候left[i][j - 1]將不能轉(zhuǎn)移原朝。
