單調(diào)棧!! 從滑動窗口說起

• • 單調(diào)棧的應(yīng)用①
  • 單調(diào)棧的應(yīng)用②

滑動窗口最大值

此題是滑動窗口中的數(shù)字個(gè)數(shù)是固定的,如果窗口中的數(shù)字個(gè)數(shù)在動態(tài)變化,比如R右邊界增加,L不變…
那有沒有一種數(shù)據(jù)結(jié)構(gòu)結(jié)構(gòu),可以讓我們以O(shè)(1)的復(fù)雜度得到此時(shí)滑動窗口中的最大值或者最小值呢???
有,那就是單調(diào)棧!!!
可以使用雙端隊(duì)列來是實(shí)現(xiàn)

該單調(diào)棧中保證從頭部到尾部保證數(shù)據(jù)的嚴(yán)格遞增或遞減;
(不允許存在相等的)

當(dāng)R往右移動一個(gè)位置時(shí),如果此時(shí)R位置的數(shù),滿足單調(diào)中的嚴(yán)格遞增或遞減順序,則放入到隊(duì)列尾部
如果不滿足,則依次彈出隊(duì)列尾部的值,直到放入的數(shù)滿足嚴(yán)格遞增或遞減的順序

當(dāng)L往右動時(shí),如果L此時(shí)的位置,是雙端隊(duì)列頭部的值,則刪除頭部的值

單調(diào)棧為什么能以O(shè)(1)的復(fù)雜度得到滑動窗口中的最大值或者最小值呢???
因?yàn)樗S護(hù)的是信息是:

當(dāng)R不往右動時(shí),L此時(shí)位置的數(shù)過期,該窗口中誰會成為最大值的順序;

比如 6 5 4 3 5 ,此時(shí)L下標(biāo)為-1, R下標(biāo)為3

此時(shí)隊(duì)列為
6 5 4 3
如果L往右動,那么滑動窗口中成為最大值為5
再往右動最大值為4

分析一下為什么?
當(dāng)R往右動,即窗口此時(shí)又包含了5,此時(shí)單調(diào)棧中需要把3,4移除隊(duì)列
因?yàn)楦鶕?jù)單調(diào)棧維護(hù)的信息,知道
我5比3,4都要大,而且我要晚過期,所以,只要有我5在,3,4就可能成為此時(shí)窗口的最大值,因此可以把它們移除
分析一下時(shí)間復(fù)雜度:
所有元素進(jìn)出單調(diào)棧(雙端隊(duì)列一次),因此是O(n),每個(gè)元素評價(jià)下來就是O(n)/n相對于O(1)

以下是通用代碼,即窗口值不固定,當(dāng)我們R往右移動時(shí),調(diào)用addNumFromRight方法即可
當(dāng)L往右移動時(shí),調(diào)用WindoxMax中的RemovenumFromLeft

單調(diào)棧的應(yīng)用①

如果給定一個(gè)數(shù)組,我們想知道每一個(gè)數(shù),左邊比它大的且離它最近,右邊比它的且離它最近的數(shù)分別是什么???

常規(guī)方法是,遍歷這個(gè)數(shù)的左邊和右邊,可以得到結(jié)果,但是這樣時(shí)間復(fù)雜度是O(n2)
這題我們可以利用單調(diào)棧把整體復(fù)雜度降低為O(n)

先考慮數(shù)組中不出現(xiàn)重復(fù)值的情況
由于這里是要找左邊,右邊最近且最大的值,因此這里維護(hù)一個(gè)從底部到頂部從大到小的順序,如果滿足單調(diào)棧的遞減順序,就壓入棧,如果不滿足,則彈出棧頂元素,并且生成棧頂元素的信息,左邊離你最近且最大的就是該元素下面一個(gè)(這里是4),右邊最近最大的就是讓你彈出的那個(gè)元素(這里是6)

接著由于6比4大,繼續(xù)彈出,生成信息

6比5大,繼續(xù)彈出生成信息

…
如果到最后棧中還有元素,則進(jìn)入清算階段
從棧頂開始彈出元素,右邊最近最大的沒有,左邊最近最大的就是該元素下面的元素;

這樣的時(shí)間復(fù)雜度是O(n)的,因?yàn)閿?shù)組中元素只會進(jìn)出單調(diào)棧一次

接下來證明:
假設(shè)此時(shí)數(shù)組中沒有重復(fù)值,數(shù)組時(shí)從左往右進(jìn)入棧
此時(shí)要壓入c,c比a大,此時(shí)要彈出a并且生成a的信息
①為什么當(dāng)a彈出時(shí),數(shù)組右邊離a最近且最大的一定是c

假設(shè)如果數(shù)組中,a 和 c之間有比a大的數(shù)k,由于數(shù)組時(shí)從左往右遍歷的,當(dāng)我們遍歷到k的時(shí)候,就會把a(bǔ)彈出了,并且生成a的信息,但是現(xiàn)在是輪到c來把a(bǔ)彈出,這就說明此時(shí)c已經(jīng)是a右邊最近且最大的值了

②為什么當(dāng)a彈出時(shí),數(shù)組左邊離a最近且最大的一定是b
同樣假設(shè)如果原數(shù)組中中a和b之間有其他數(shù),假設(shè)存在一個(gè)k
b … k …a
那么k有可能有以下3種情況:

k > b : 這種情況不可能存在,因?yàn)槿绻鹝>b,那么k就已經(jīng)把b給替換了

a < k < b : 這種情況也不可能,因?yàn)榇藭r(shí)a,b不可能挨著一起,你也許回想,有可能來了一個(gè)比k大的數(shù),然后把k給替換了,但是我們這里是無重復(fù)值的情況,因此你無論怎么替換最終不可能把b給替換了,即單調(diào)棧在a,b之間夾了一個(gè)數(shù),因此這種情況不存在

k < a: 這種情況就允許存在了,因?yàn)槿绻瓟?shù)組中b,a之間全是比a小的數(shù),那么最終就會形成單調(diào)棧的情況 a在b之上;
所以: 可證明,當(dāng)彈出a時(shí),a左邊比a大的且最近的就是b,即單調(diào)棧維護(hù)的信息時(shí)正確的!!

代碼
這里代碼展示的是找一個(gè)數(shù)字,左邊小于它并且最近的數(shù),右邊小于它并且最近的數(shù),那么我們只需要保持單調(diào)棧從底部到頭部是遞增即可

public static int[][] getNearLessNoRepeat(int[] arr) {int[][] res = new int[arr.length][2];Stack<Integer> stack = new Stack<>();for (int i = 0; i < arr.length; i++) {while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {int popIndex = stack.pop();int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();res[popIndex][0] = leftLessIndex;res[popIndex][1] = i;}stack.push(i);}while (!stack.isEmpty()) {int popIndex = stack.pop();int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();res[popIndex][0] = leftLessIndex;res[popIndex][1] = -1;}return res;}

此時(shí)來看看如果數(shù)組中有重復(fù)值
如果有重復(fù)值,那么只需要把相同值的下標(biāo)放在一起,串成一個(gè)鏈表!!

比如: 此時(shí)來了一個(gè)6位置的5,此時(shí)要彈出5位置的3,那么右邊比3大的數(shù)且最近的 就是6位置的5
左邊比3大的就是相同值為5串成的鏈表的最后一個(gè),也就是4位置的5

代碼:

public static int[][] getNearLess(int[] arr) {int[][] res = new int[arr.length][2];Stack<List<Integer>> stack = new Stack<>();for (int i = 0; i < arr.length; i++) {while (!stack.isEmpty() && arr[stack.peek().get(0)] > arr[i]) {List<Integer> popIs = stack.pop();// 取位于下面位置的列表中，最晚加入的那個(gè)int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);for (Integer popi : popIs) {res[popi][0] = leftLessIndex;res[popi][1] = i;}}if (!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]) {stack.peek().add(Integer.valueOf(i));} else {ArrayList<Integer> list = new ArrayList<>();list.add(i);stack.push(list);}}while (!stack.isEmpty()) {List<Integer> popIs = stack.pop();// 取位于下面位置的列表中，最晚加入的那個(gè)int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);for (Integer popi : popIs) {res[popi][0] = leftLessIndex;res[popi][1] = -1;}}return res;}

單調(diào)棧的應(yīng)用②

一個(gè)數(shù)組中子數(shù)組的累計(jì)和與最小值的乘積叫作指標(biāo)A,給定一個(gè)正數(shù)數(shù)組,
請返回這個(gè)數(shù)組中,A的最大值

算法部分看max2方法,max1方法是用的暴力法,用對數(shù)器來驗(yàn)證max2是否是正確的!!!

public class Code03_AllTimesMinToMax {public static int max1(int[] arr) {int max = Integer.MIN_VALUE;for (int i = 0; i < arr.length; i++) {for (int j = i; j < arr.length; j++) {int minNum = Integer.MAX_VALUE;int sum = 0;for (int k = i; k <= j; k++) {sum += arr[k];minNum = Math.min(minNum, arr[k]);}max = Math.max(max, minNum * sum);}}return max;}public static int max2(int[] arr) {int size = arr.length;int[] sums = new int[size];sums[0] = arr[0];for (int i = 1; i < size; i++) {sums[i] = sums[i - 1] + arr[i];}int max = Integer.MIN_VALUE;Stack<Integer> stack = new Stack<Integer>();for (int i = 0; i < size; i++) {while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {int j = stack.pop();max = Math.max(max, (stack.isEmpty() ? sums[i - 1] : (sums[i - 1] - sums[stack.peek()])) * arr[j]);}stack.push(i);}while (!stack.isEmpty()) {int j = stack.pop();max = Math.max(max, (stack.isEmpty() ? sums[size - 1] : (sums[size - 1] - sums[stack.peek()])) * arr[j]);}return max;}public static int[] gerenareRondomArray() {int[] arr = new int[(int) (Math.random() * 20) + 10];for (int i = 0; i < arr.length; i++) {arr[i] = (int) (Math.random() * 101);}return arr;}public static void main(String[] args) {int testTimes = 2000000;for (int i = 0; i < testTimes; i++) {int[] arr = gerenareRondomArray();if (max1(arr) != max2(arr)) {System.out.println("FUCK!");break;}}}

總結(jié)

以上是生活随笔為你收集整理的单调栈的应用的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。