一种特别设计的栈结构，为了解决如下的问题：

给定一个可能含有重复值的数组arr，i位置的数一定存在如下两个信息
1）arr[i]的左侧离i最近并且小于(或者大于)arr[i]的数在哪？
2）arr[i]的右侧离i最近并且小于(或者大于)arr[i]的数在哪？
如果想得到arr中所有位置的两个信息，怎么能让得到信息的过程尽量快。

习题1 单调栈的实现

	// 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;}// for testpublic static int[] getRandomArrayNoRepeat(int size) {int[] arr = new int[(int) (Math.random() * size) + 1];for (int i = 0; i < arr.length; i++) {arr[i] = i;}for (int i = 0; i < arr.length; i++) {int swapIndex = (int) (Math.random() * arr.length);int tmp = arr[swapIndex];arr[swapIndex] = arr[i];arr[i] = tmp;}return arr;}// for testpublic static int[] getRandomArray(int size, int max) {int[] arr = new int[(int) (Math.random() * size) + 1];for (int i = 0; i < arr.length; i++) {arr[i] = (int) (Math.random() * max) - (int) (Math.random() * max);}return arr;}// for testpublic static int[][] rightWay(int[] arr) {int[][] res = new int[arr.length][2];for (int i = 0; i < arr.length; i++) {int leftLessIndex = -1;int rightLessIndex = -1;int cur = i - 1;while (cur >= 0) {if (arr[cur] < arr[i]) {leftLessIndex = cur;break;}cur--;}cur = i + 1;while (cur < arr.length) {if (arr[cur] < arr[i]) {rightLessIndex = cur;break;}cur++;}res[i][0] = leftLessIndex;res[i][1] = rightLessIndex;}return res;}// for testpublic static boolean isEqual(int[][] res1, int[][] res2) {if (res1.length != res2.length) {return false;}for (int i = 0; i < res1.length; i++) {if (res1[i][0] != res2[i][0] || res1[i][1] != res2[i][1]) {return false;}}return true;}// for testpublic static void printArray(int[] arr) {for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}public static void main(String[] args) {int size = 10;int max = 20;int testTimes = 2000000;System.out.println("测试开始");for (int i = 0; i < testTimes; i++) {int[] arr1 = getRandomArrayNoRepeat(size);int[] arr2 = getRandomArray(size, max);if (!isEqual(getNearLessNoRepeat(arr1), rightWay(arr1))) {System.out.println("Oops!");printArray(arr1);break;}if (!isEqual(getNearLess(arr2), rightWay(arr2))) {System.out.println("Oops!");printArray(arr2);break;}}System.out.println("测试结束");}

习题2 给定一个只包含正数的数组arr，arr中任何一个子数组sub，一定都可以算出(sub累加和 )* (sub中的最小值)是什么，那么所有子数组中，这个值最大是多少？

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);}

习题3 给定一个非负数组arr，代表直方图 返回直方图的最大长方形面积

public static int largestRectangleArea1(int[] height) {if (height == null || height.length == 0) {return 0;}int maxArea = 0;Stack<Integer> stack = new Stack<Integer>();for (int i = 0; i < height.length; i++) {while (!stack.isEmpty() && height[i] <= height[stack.peek()]) {int j = stack.pop();int k = stack.isEmpty() ? -1 : stack.peek();int curArea = (i - k - 1) * height[j];maxArea = Math.max(maxArea, curArea);}stack.push(i);}while (!stack.isEmpty()) {int j = stack.pop();int k = stack.isEmpty() ? -1 : stack.peek();int curArea = (height.length - k - 1) * height[j];maxArea = Math.max(maxArea, curArea);}return maxArea;}public static int largestRectangleArea2(int[] height) {if (height == null || height.length == 0) {return 0;}int N = height.length;int[] stack = new int[N];int si = -1;int maxArea = 0;for (int i = 0; i < height.length; i++) {while (si != -1 && height[i] <= height[stack[si]]) {int j = stack[si--];int k = si == -1 ? -1 : stack[si];int curArea = (i - k - 1) * height[j];maxArea = Math.max(maxArea, curArea);}stack[++si] = i;}while (si != -1) {int j = stack[si--];int k = si == -1 ? -1 : stack[si];int curArea = (height.length - k - 1) * height[j];maxArea = Math.max(maxArea, curArea);}return maxArea;}

习题4 给定一个二维数组matrix，其中的值不是0就是1，返回全部由1组成的最大子矩形，内部有多少个1

public static int maximalRectangle(char[][] map) {if (map == null || map.length == 0 || map[0].length == 0) {return 0;}int maxArea = 0;int[] height = new int[map[0].length];for (int i = 0; i < map.length; i++) {for (int j = 0; j < map[0].length; j++) {height[j] = map[i][j] == '0' ? 0 : height[j] + 1;}maxArea = Math.max(maxRecFromBottom(height), maxArea);}return maxArea;}// height是正方图数组public static int maxRecFromBottom(int[] height) {if (height == null || height.length == 0) {return 0;}int maxArea = 0;Stack<Integer> stack = new Stack<Integer>();for (int i = 0; i < height.length; i++) {while (!stack.isEmpty() && height[i] <= height[stack.peek()]) {int j = stack.pop();int k = stack.isEmpty() ? -1 : stack.peek();int curArea = (i - k - 1) * height[j];maxArea = Math.max(maxArea, curArea);}stack.push(i);}while (!stack.isEmpty()) {int j = stack.pop();int k = stack.isEmpty() ? -1 : stack.peek();int curArea = (height.length - k - 1) * height[j];maxArea = Math.max(maxArea, curArea);}return maxArea;}

习题5 给定一个二维数组matrix，其中的值不是0就是1，返回全部由1组成的子矩形数量

public static int numSubmat(int[][] mat) {if (mat == null || mat.length == 0 || mat[0].length == 0) {return 0;}int nums = 0;int[] height = new int[mat[0].length];for (int i = 0; i < mat.length; i++) {for (int j = 0; j < mat[0].length; j++) {height[j] = mat[i][j] == 0 ? 0 : height[j] + 1;}nums += countFromBottom(height);}return nums;}// 比如//              1//              1//              1         1//    1         1         1//    1         1         1//    1         1         1//             //    2  ....   6   ....  9// 如上图，假设在6位置，1的高度为6// 在6位置的左边，离6位置最近、且小于高度6的位置是2，2位置的高度是3// 在6位置的右边，离6位置最近、且小于高度6的位置是9，9位置的高度是4// 此时我们求什么？// 1) 求在3~8范围上，必须以高度6作为高的矩形，有几个？// 2) 求在3~8范围上，必须以高度5作为高的矩形，有几个？// 也就是说，<=4的高度，一律不求// 那么，1) 求必须以位置6的高度6作为高的矩形，有几个？// 3..3  3..4  3..5  3..6  3..7  3..8// 4..4  4..5  4..6  4..7  4..8// 5..5  5..6  5..7  5..8// 6..6  6..7  6..8// 7..7  7..8// 8..8// 这么多！= 21 = (9 - 2 - 1) * (9 - 2) / 2// 这就是任何一个数字从栈里弹出的时候，计算矩形数量的方式public static int countFromBottom(int[] height) {if (height == null || height.length == 0) {return 0;}int nums = 0;int[] stack = new int[height.length];int si = -1;for (int i = 0; i < height.length; i++) {while (si != -1 && height[stack[si]] >= height[i]) {int cur = stack[si--];if (height[cur] > height[i]) {int left = si == -1 ? -1 : stack[si];int n = i - left - 1;int down = Math.max(left == -1 ? 0 : height[left], height[i]);nums += (height[cur] - down) * num(n);}}stack[++si] = i;}while (si != -1) {int cur = stack[si--];int left = si == -1  ? -1 : stack[si];int n = height.length - left - 1;int down = left == -1 ? 0 : height[left];nums += (height[cur] - down) * num(n);}return nums;}public static int num(int n) {return ((n * (1 + n)) >> 1);}