一 單調棧知識講解
1.1描述
一個數組里面想的到每個位置與他最近的左邊和右邊比他小的最近的信息
1.2 分析
通過單調棧的特點，for遍歷數組中的每個數，當前數來的時候對比單調棧中的數進行每個數的左右判斷完滿足條件的進行更新到當前i種的
int[][] res = new int[arr.length][2]; 里0和1中去
res[j][0] = leftLessIndex;
res[j][1] = i;
1.2.1 無重復值版本
1.2.2 有重復值版本
1.3 代碼
無重復值情況
// arr = [ 3, 1, 2, 3]// 0 1 2 3// [// 0 : [-1, 1]// 1 : [-1, -1]// 2 : [ 1, -1]// 3 : [ 2, -1]// ]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++) { // 當遍歷到i位置的數，arr[i]while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {int j = stack.pop();int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();res[j][0] = leftLessIndex;res[j][1] = i;}stack.push(i);}while (!stack.isEmpty()) {int j = stack.pop();int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();res[j][0] = leftLessIndex;res[j][1] = -1;}return res;}
有重復值情況
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++) { // i -> arr[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;}
二 單調棧應用實例1
2.1 描述
給定一個只包含正數的數組arr，arr中任何一個子數組sub， 一定都可以算出(sub累加和 )* (sub中的最小值)是什么， 那么所有子數組中（子數組的index一定是連續的），這個值最大是多少？
2.2 分析
如果我們求出必須以每個位置為最小值情況下的答案，那么我們整體答案一定在其中
首先以當前index為作為最小值的子數組，看他的指標值是多少，依次for，答案一定在其中將max選出來就行了
如果子數組我必須以X為最小值，我如何能夠得到他以哪個子數組他的累加和最大呢，也就是找到左邊離你最近的比你最小的，右邊離你最近的比你小的，中間包含x整個這段全要就是X為最小值累加和最大的子數組
2.3 代碼
package class25;import java.util.Stack;public class Code02_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;System.out.println("test begin");for (int i = 0; i < testTimes; i++) {int[] arr = gerenareRondomArray();if (max1(arr) != max2(arr)) {System.out.println("FUCK!");break;}}System.out.println("test finish");}// 本題可以在leetcode上找到原題// 測試鏈接 : https://leetcode.com/problems/maximum-subarray-min-product/// 注意測試題目數量大，要取模，但是思路和課上講的是完全一樣的// 注意溢出的處理即可，也就是用long類型來表示累加和// 還有優化就是，你可以用自己手寫的數組棧，來替代系統實現的棧，也會快很多public static int maxSumMinProduct(int[] arr) {int size = arr.length;long[] sums = new long[size];sums[0] = arr[0];for (int i = 1; i < size; i++) {sums[i] = sums[i - 1] + arr[i];}long max = Long.MIN_VALUE;int[] stack = new int[size];int stackSize = 0;for (int i = 0; i < size; i++) {while (stackSize != 0 && arr[stack[stackSize - 1]] >= arr[i]) {int j = stack[--stackSize];max = Math.max(max,(stackSize == 0 ? sums[i - 1] : (sums[i - 1] - sums[stack[stackSize - 1]])) * arr[j]);}stack[stackSize++] = i;}while (stackSize != 0) {int j = stack[--stackSize];max = Math.max(max,(stackSize == 0 ? sums[size - 1] : (sums[size - 1] - sums[stack[stackSize - 1]])) * arr[j]);}return (int) (max % 1000000007);}}
