單調棧!! 從滑動視窗說起
- 單調棧的應用①
- 單調棧的應用②
滑動視窗最大值
此題是滑動視窗中的數字個數是固定的,如果視窗中的數字個數在動态變化,比如R右邊界增加,L不變…
那有沒有一種資料結構結構,可以讓我們以O(1)的複雜度得到此時滑動視窗中的最大值或者最小值呢???
有,那就是單調棧!!!
可以使用雙端隊列來是實作
該單調棧中保證從頭部到尾部保證資料的嚴格遞增或遞減;
(不允許存在相等的)
當R往右移動一個位置時,如果此時R位置的數,滿足單調中的嚴格遞增或遞減順序,則放入到隊列尾部
如果不滿足,則依次彈出隊列尾部的值,直到放入的數滿足嚴格遞增或遞減的順序
當L往右動時,如果L此時的位置,是雙端隊列頭部的值,則删除頭部的值
單調棧為什麼能以O(1)的複雜度得到滑動視窗中的最大值或者最小值呢???
因為它維護的是資訊是:
當R不往右動時,L此時位置的數過期,該視窗中誰會成為最大值的順序;
比如 6 5 4 3 5 ,此時L下标為-1, R下标為3
此時隊列為
6 5 4 3
如果L往右動,那麼滑動視窗中成為最大值為5
再往右動最大值為4
分析一下為什麼?
當R往右動,即視窗此時又包含了5,此時單調棧中需要把3,4移除隊列
因為根據單調棧維護的資訊,知道
我5比3,4都要大,而且我要晚過期,是以,隻要有我5在,3,4就可能成為此時視窗的最大值,是以可以把它們移除
分析一下時間複雜度:
所有元素進出單調棧(雙端隊列一次),是以是O(n),每個元素評價下來就是O(n)/n相對于O(1)
以下是通用代碼,即視窗值不固定,當我們R往右移動時,調用addNumFromRight方法即可
當L往右移動時,調用WindoxMax中的RemovenumFromLeft
單調棧的應用①
如果給定一個數組,我們想知道每一個數,左邊比它大的且離它最近,右邊比它的且離它最近的數分别是什麼???
正常方法是,周遊這個數的左邊和右邊,可以得到結果,但是這樣時間複雜度是O(n2)
這題我們可以利用單調棧把整體複雜度降低為O(n)
先考慮數組中不出現重複值的情況
由于這裡是要找左邊,右邊最近且最大的值,是以這裡維護一個從底部到頂部從大到小的順序,如果滿足單調棧的遞減順序,就壓入棧,如果不滿足,則彈出棧頂元素,并且生成棧頂元素的資訊,左邊離你最近且最大的就是該元素下面一個(這裡是4),右邊最近最大的就是讓你彈出的那個元素(這裡是6)
接着由于6比4大,繼續彈出,生成資訊
6比5大,繼續彈出生成資訊
…
如果到最後棧中還有元素,則進入清算階段
從棧頂開始彈出元素,右邊最近最大的沒有,左邊最近最大的就是該元素下面的元素;
這樣的時間複雜度是O(n)的,因為數組中元素隻會進出單調棧一次
接下來證明:
假設此時數組中沒有重複值,數組時從左往右進入棧
此時要壓入c,c比a大,此時要彈出a并且生成a的資訊
①為什麼當a彈出時,數組右邊離a最近且最大的一定是c
假設如果數組中,a 和 c之間有比a大的數k,由于數組時從左往右周遊的,當我們周遊到k的時候,就會把a彈出了,并且生成a的資訊,但是現在是輪到c來把a彈出,這就說明此時c已經是a右邊最近且最大的值了
②為什麼當a彈出時,數組左邊離a最近且最大的一定是b
同樣假設如果原數組中中a和b之間有其他數,假設存在一個k
b … k …a
那麼k有可能有以下3種情況:
- k > b : 這種情況不可能存在,因為如果k>b,那麼k就已經把b給替換了
- a < k < b : 這種情況也不可能,因為此時a,b不可能挨着一起,你也許回想,有可能來了一個比k大的數,然後把k給替換了,但是我們這裡是無重複值的情況,是以你無論怎麼替換最終不可能把b給替換了,即單調棧在a,b之間夾了一個數,是以這種情況不存在
-
k < a: 這種情況就允許存在了,因為如果原數組中b,a之間全是比a小的數,那麼最終就會形成單調棧的情況 a在b之上;
是以: 可證明,當彈出a時,a左邊比a大的且最近的就是b,即單調棧維護的資訊時正确的!!
代碼
這裡代碼展示的是找一個數字,左邊小于它并且最近的數,右邊小于它并且最近的數,那麼我們隻需要保持單調棧從底部到頭部是遞增即可
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;
}
此時來看看如果數組中有重複值
如果有重複值,那麼隻需要把相同值的下标放在一起,串成一個連結清單!!
比如: 此時來了一個6位置的5,此時要彈出5位置的3,那麼右邊比3大的數且最近的 就是6位置的5
左邊比3大的就是相同值為5串成的連結清單的最後一個,也就是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();
// 取位于下面位置的清單中，最晚加入的那個
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();
// 取位于下面位置的清單中，最晚加入的那個
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;
}
單調棧的應用②
一個數組中子數組的累計和與最小值的乘積叫作名額A,給定一個正數數組,
請傳回這個數組中,A的最大值
算法部分看max2方法,max1方法是用的暴力法,用對數器來驗證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;
}
}
}