【算法&数据结构体系篇class25 26】：单调栈技巧

Myth丶恋晨 2024-03-23 10:49 46阅读 0赞

### 一、单调栈是什么？ ###

> 一种特别设计的栈结构，为了解决如下的问题：
> 
> 给定一个可能含有重复值的数组arr，i位置的数一定存在如下两个信息
> 
> 1）arr\[i\]的左侧离i最近并且小于(或者大于)arr\[i\]的数在哪？
> 
> 2）arr\[i\]的右侧离i最近并且小于(或者大于)arr\[i\]的数在哪？
> 
> 如果想得到arr中所有位置的两个信息，怎么能让得到信息的过程尽量快。
> 
> 那么到底怎么设计呢？

### 二、单调栈的实现 ###

package class25;
    
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Stack;
    
    /**
     * 一种特别设计的栈结构，为了解决如下的问题：
     *
     * 给定一个可能含有重复值的数组arr，i位置的数一定存在如下两个信息
     * 1）arr[i]的左侧离i最近并且小于(或者大于)arr[i]的数在哪？
     * 2）arr[i]的右侧离i最近并且小于(或者大于)arr[i]的数在哪？
     * 如果想得到arr中所有位置的两个信息，怎么能让得到信息的过程尽量快。
     *
     * 那么到底怎么设计呢？
     * 返回一个二维数组  第0行就放 原数组第0个的 [左边最近且小于的值与右边最近且小于的值]
     * 	// arr = [ 3, 1, 2, 3]
     * 	//         0  1  2  3
     * 	//  [
     * 	//     0 : [-1,  1]
     * 	//     1 : [-1, -1]
     * 	//     2 : [ 1, -1]
     * 	//     3 : [ 2, -1]
     * 	//  ]
     */
    public class MonotonousStack {
    
        //方式一： arr不存在重复的值的情况下
        public static int[][] getNearLessNoRepeat(int[] arr) {
            //定义一个结果集 res 二维数组 N*2  每一行存放对应数组值的 左侧最近小 和右侧最近小的值
            int[][] res = new int[arr.length][2];
            //定义一个单调栈，栈底小 栈顶大 排序 注意存放的是数值索引
            Stack<Integer> stack = new Stack<>();
            for(int i = 0; i < arr.length; i++){
                //遍历数组每个值  入栈前判断栈中是否非空 非空 并且栈顶如果大于当前的数值i
                //需要弹出栈顶值， 因为当前数值i比他小 并且晚入栈 是在右侧的 所以就是栈顶值的右侧最近小的值 弹出 刷新
                while (!stack.isEmpty() && arr[stack.peek()] > arr[i]){
                    int pop = stack.pop();   //弹出该栈顶值 进行清算其左右侧最近的较小值
                    int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();   //左侧最近 较小 就在前面弹出后的下一个值 也就是紧挨着的一个值 前面弹出后 他也来到栈顶 假如弹出后栈空了 那说明就没有左侧的小值 返回-1
                    res[pop][0] = leftLessIndex;    //刷新弹出的值 pop索引位置行 左边值
                    res[pop][1] = i;                //刷新  右边小值  当前i位置就是其值
                }
                //如果不在前面的情况下的 就直接入栈
                stack.push(i);
            }
    
            //最后 可能会在栈里面还存在的一些未被弹出的值，也就是说 右侧的值没有存在小于的值所以需要手动弹出 右侧值赋值-1 表示没有存在右侧的小值
            while (!stack.isEmpty()){
                int pop = stack.pop();
                int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();  //刷新左侧小值，就是前面弹出后 紧挨着的值 当前来到了栈顶了
                res[pop][0] = leftLessIndex;
                res[pop][1] = -1;
            }
            return res;
        }
    
        //方式一：arr存在重复的值的情况下
        public static int[][] getNearLess(int[] arr) {
            //定义一个结果集 res 二维数组 N*2  每一行存放对应数组值的 左侧最近小 和右侧最近小的值
            int[][] res = new int[arr.length][2];
            //定义一个单调栈，栈底小 栈顶大 排序 注意存放的是list集合 元素是数值索引 一个list中存放的就是值相等的多个索引值
            Stack<List<Integer>> stack = new Stack<>();
    
            //开发遍历数组的值
            for(int i = 0; i < arr.length; i++){
                //当前栈不为空 且i值 比栈顶的集合元素值小 元素取0位置其一都可以，因为集合里面都是值一样的     那么就表示找到该栈顶值得 右侧小值 就将其弹出 刷新左右侧小值
                while(!stack.isEmpty() && arr[stack.peek().get(0)] > arr[i]){
                    List<Integer> pop = stack.pop();
                    int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size()-1);  //刷新左侧小值 弹出元素后紧挨着后面的值,需要取集合中最后一个索引 才是最靠近的小值 如果空就表示没有返回-1
                    //遍历弹出的集合 每个集合值都相等 所以刷新左右侧的小值都一样的
                    for(int index : pop){
                        res[index][0] = leftLessIndex;
                        res[index][1] = i;
                    }
                }
    
                //栈非空 如果说当前i值 是等于栈顶的  那么就把他加入栈顶集合中 因为值相等 就放在一个集合中
                if(!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]){
                    stack.peek().add(i);
                }else {
                    //否则 那就是 大于栈顶 或者栈空 那么都直接入栈
                    ArrayList<Integer> list = new ArrayList<>();  //用arraylist 在get()元素会比linkedlist更快 链表要从头开始 arraylist能直接找到
                    list.add(i);
                    stack.push(list);
                }
            }
    
            //接着将栈中还没弹出刷新的值 进行弹出 刷新  栈中有值没弹出 说明右侧没有遇到小值 所以右侧小值都是-1表示不存在
            while (!stack.isEmpty()){
                List<Integer> pop = stack.pop();
                int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size()-1);  刷新左侧小值 弹出元素后紧挨着后面的值,需要取集合中最后一个索引 才是最靠近的小值 如果空就表示没有返回-1
                for(int index:pop){
                    res[index][0] = leftLessIndex;   //刷新左侧小值
                    res[index][1] = -1;   //栈中的值 右侧都不存在小值得 返回-1
                }
            }
            return res;
        }
    
        // for test
        public 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 test
        public 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 test
        public 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 test
        public 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 test
        public 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("测试结束");
        }
    }

###  ###

### 三、题目一 ###

### 给定一个只包含正数的数组arr，arr中任何一个子数组sub， ###

### 一定都可以算出(sub累加和 )\* (sub中的最小值)是什么， ###

### 那么所有子数组中，这个值最大是多少？ ###

package class25;
    
    import java.util.Arrays;
    import java.util.Stack;
    
    /**
     * 给定一个只包含正数的数组arr，arr中任何一个子数组sub，
     * 一定都可以算出(sub累加和 )* (sub中的最小值)是什么，
     * 那么所有子数组中，这个值最大是多少？
     */
    public class 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) {
            //题目需要用到累加和 可以预处理一个前缀和数组 后续就可以直接O(1)得到某个子数组sub的累加和
            int size = arr.length;          //数组长度
            int[] sums = new int[size];     //前缀和数组 长度等长arr原数组
    
            sums[0] = arr[0];               //前缀和数组填充
            for(int i = 1; i < size; i++){
                sums[i] = arr[i] + sums[i-1];
            }
    
            //定义一个栈，单调栈 根据题意每个sub的最小值  所以定义栈底到栈顶 从小到大排序 每个值作为最小值入栈
            Stack<Integer> stack = new Stack<>();
            int max = Integer.MIN_VALUE;       //初始定义结果值 最小值 返回所有sub数组 累加和*最小值的 结果的最大值
            //遍历整个数组
            for(int i = 0; i < size; i++){
                while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]){
                    //刷新单调栈 滑动窗口   非空，并且栈顶大于等于数组当前值i 就弹出栈顶值 该值最为最小值 进行计算其sub子数组所求的累加和 *自身
                    //这里注意 为什么相等的也要算进去  大于的好理解：栈顶下个元素就是当前i 如果栈顶大于i 根据我们设计的是每个值入栈做sub数组的最小值
                    //右侧出现了小于自己的值 那么就肯定要弹出计算了，sub数组就是 (栈顶后一个值，i值） 左右都开区间 边界是到不了的 为了确保sub在当前栈顶是最小值
                    //而相等算进去 可能会计算错。按照这个逻辑 sub数组也就是 (栈顶后一个值，i值） 左侧是对的 右侧呢 i值是相等的 再往右可能也有符合的值，比自己大的值 需要计算到sub中
                    //此时的值算错没关系  因为等到后面出现最后一个重复值相等的时候 该位置就是能算得到一个对的sub范围 而最小值仍是这个重复值。 这个结果集会覆盖我们的max 值 所以不影响
                    int pop = stack.pop();
                    //刷新最大值：  如果前面弹出值后 栈空了 说明值左侧都是符合的 没有小于自己的值 sub数组累加和就把当前i-1位置开始前面的都累加上 sum[i-1]
                    //如果非空 说明左侧存在小于的值 那么sub子数组就把当前来到栈顶的位置前面的累计和减去 sums[qmin.peek()]   然后再乘以当前弹出的值 刷新最大值
                    max = Math.max(max, (stack.isEmpty() ? sums[i-1] : sums[i-1] - sums[stack.peek()])*arr[pop]);
                }
                stack.push(i);  //如果不存在前面的情况 就直接索引入栈
            }
    
            //最后将栈中还有存在的值进行处理 还在栈 说明右侧没有比自己小的值，才没有被弹出的  子数组最右侧就是来到数组的最后元素 size-1位置
            //右侧就判断 弹出一个栈顶后 栈中是否还有值 如果没有值 说明左侧也没有比自己小的值 那么子数组就是整个数组累加和
            //如果栈中有值，那么说明弹出后 当前来到栈顶的位置是比自己小的 累加和就要减去 该栈顶值位置到数组前面的累加和
            //累加和求完之后再乘以 弹出的值 刷新最大值
            while (!stack.isEmpty()){
                int pop = stack.pop();
                max =  Math.max(max, (stack.isEmpty() ? sums[size-1] : sums[size-1] - sums[stack.peek()])*arr[pop]);
            }
            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!");
                    System.out.println(Arrays.toString(arr));
                    break;
                }
            }
            System.out.println("test finish");
        }
    
    
        // 本题可以在leetcode上找到原题
        // 测试链接 : https://leetcode.com/problems/maximum-subarray-min-product/
        // 注意测试题目数量大，要取模，但是思路和课上讲的是完全一样的
        // 注意溢出的处理即可，也就是用long类型来表示累加和
        // 还有优化就是，你可以用自己手写的数组栈，来替代系统实现的栈，也会快很多
        public int maxSumMinProduct(int[] nums) {
            int size = nums.length;
            long[] sums = new long[size];      //定义前缀和数组 注意题目提到数可能很大 用long型
            sums[0] = nums[0];
            for(int i = 1; i < size; i++){
                sums[i] = nums[i] + sums[i-1];
            }
    
            int[] stack = new int[size];      //定义一个长度跟nums一致的 数组栈 保存的是每个值的索引 从小到大
            int stackSize = 0;                     //初始化定义栈中的元素 一开始是0
            long max = Long.MIN_VALUE;        //题意提及数可能很大 用long类型的最小值
    
            for(int i = 0; i < size; i++){
                while (stackSize != 0 && nums[stack[stackSize -1]] >= nums[i]){
                    //数组栈大小不为0  数组尾部值 就是stackSize -1位置 大于等于 当前i 那么就弹出这个值，并且将栈大小-1  要先--，因为stackSize
                    // 是数组大小 是比下标大1的
                    // 对弹出的值 作为最小值 找到其子数组累加和  计算其最小乘积
                    int pop = stack[--stackSize];
                    //刷新最大值  以弹出的值为最小值 取出其所在的子数组  先判断弹出后 栈中如果为空 那么该值的子数组范围就是 从0...i-1累加和 左边都是大于他的值
                    //栈非空 说明下个值就是小于其弹出的值 那么子数组范围 要确保弹出值最小 范围就是从 stack[stackSize-1] ， i-1 不包括左边的值 也就是减去0..stack[stackSize-1]
                   //子数组累加和得到后 再乘以当前弹出的作为最小值的值nums[pop]
                    max = Math.max(max, (stackSize == 0 ? sums[i-1] : sums[i-1] - sums[stack[stackSize-1]]) * nums[pop]);
                }
                //数组栈大小0 或者 当前栈尾值 小于当前i值 直接插入,同时栈大小+1
                stack[stackSize++] = i;
            }
    
            //最后还在数组栈中的值，也需要提出更新 说明其右侧的值都是大于这些栈中的值的
            //所以这些值作为最小值 子数组的右边界就是到数组最后一个值
            while(stackSize != 0){
                int pop = stack[--stackSize];
                max = Math.max(max, (stackSize == 0 ? sums[size-1] : sums[size-1] - sums[stack[stackSize-1]]) * nums[pop]);
            }
            return (int) (max % 1000000007);
        }
    
    }

### 四、题目二 ###

### 给定一个非负数组arr，代表直方图 ###

### 返回直方图的最大长方形面积 ###

package class25;
    
    import java.util.Stack;
    
    /**
     * 给定一个非负数组arr，代表直方图
     * 返回直方图的最大长方形面积
     * // 测试链接：https://leetcode.cn/problems/largest-rectangle-in-histogram/
     */
    public class LargestRectangleInHistogram {
    
        //方式一 ： 利用系统栈结构 单调栈
        public static int largestRectangleArea1(int[] heights) {
            //边界判断
            if(heights == null || heights.length == 0) return 0;
    
            //定义栈结构，单调栈 栈底到栈顶 从小到大排序
            Stack<Integer> stack = new Stack<>();
            //结果范围值 初始为0
            int maxArea = 0;
    
            //遍历数组
            for(int i = 0; i < heights.length; i++){
                while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]){
                    //栈非空 且栈顶值大于等于 当前i值 那么就弹出栈顶
                    int pop = stack.pop();   //代表高度
                    //求其所在最大长方形的宽度范围  如果栈空，那么表示左边界就没有值小于他，所以索引定义-1
                    //非空 那么当前栈顶就是左边界  （stack.peek(), height[i]） 左右都是开区间 不包含两边的值
                    int widthIndex = stack.isEmpty() ? -1 : stack.peek();
                    //刷新面积最大值  pop是高度索引 高度是height[pop]  宽度就是两边范围中间的个数  右边i 左边widthIndex  减去后 还需要再-1 才是中间的个数
                    maxArea = Math.max(maxArea, (i - widthIndex - 1)* heights[pop]);
                }
                //栈空 或者当前值大于栈顶值 直接入栈
                stack.push(i);
            }
    
            //最后如果栈中还存在数 需要进行刷新最大面积  既然没有被弹出 说明右侧的值都是大于栈中值
            //所以这个长方形 右边就能够到数组最后一个元素的位置
            while(!stack.isEmpty()){
                int pop = stack.pop();
                int widthIndex = stack.isEmpty() ? -1 : stack.peek();
                //刷新面积值 右侧边界就是 height.length  包含该边界 左边的边界是不包含的
                maxArea = Math.max(maxArea, (heights.length - widthIndex -1)* heights[pop]);
            }
            return maxArea;
        }
    
        //方式二 ： 手写数组栈结构 单调栈  效率更高
        public static int largestRectangleArea2(int[] heights) {
            //边界判断
            if(heights == null || heights.length == 0) return 0;
    
            int size = heights.length;
            //定义数组栈结构，长度跟目标数组一致 单调栈 栈底到栈顶 从小到大排序
            int[] stack = new int[size];
            //定义数组栈的最后元素的索引 一开始没有元素 位置来到-1
            int stackIndex = -1;
            //结果范围值 初始为0
            int maxArea = 0;
    
    
            //遍历数组
            for(int i = 0; i < heights.length; i++){
                while (stackIndex != -1 && heights[stack[stackIndex]] >= heights[i]){
                    //栈非空 且栈顶值大于等于 当前i值  那么就弹出栈顶 注意索引也要--
                    int pop = stack[stackIndex--];   //代表高度
                    //求其所在最大长方形的宽度范围  如果栈空，那么表示左边界就没有值小于他，所以索引定义-1
                    //非空 那么当前栈顶就是左边界  （stack.peek(), height[i]） 左右都是开区间 不包含两边的值
                    int widthIndex = stackIndex == -1 ? -1 : stack[stackIndex];
                    //刷新面积最大值  pop是高度索引 高度是height[pop]  宽度就是两边范围中间的个数  右边i 左边widthIndex  减去后 还需要再-1 才是中间的个数
                    maxArea = Math.max(maxArea, (i - widthIndex - 1)* heights[pop]);
                }
                //栈空 或者当前值大于栈顶值 直接入栈 注意索引首次是-1 需要先++ 然后赋值
                stack[++stackIndex] = i;
            }
    
            //最后如果栈中还存在数 需要进行刷新最大面积  既然没有被弹出 说明右侧的值都是大于栈中值
            //所以这个长方形 右边就能够到数组最后一个元素的位置
            while(stackIndex != -1){
                int pop = stack[stackIndex--];
                int widthIndex = stackIndex == -1 ? -1 : stack[stackIndex];
                //刷新面积值 右侧边界就是 height.length  包含该边界 左边的边界是不包含的
                maxArea = Math.max(maxArea, (heights.length - widthIndex -1)* heights[pop]);
            }
            return maxArea;
        }
    }

###  ###

### 五、题目三 ###

### 给定一个二维数组matrix，其中的值不是0就是1， ###

### 返回全部由1组成的最大子矩形，内部有多少个1 ###

package class25;
    
    import java.util.Stack;
    
    /**
     * 给定一个二维数组matrix，其中的值不是0就是1，
     * 返回全部由1组成的最大子矩形，内部有多少个1
     *
     * // 测试链接：https://leetcode.cn/problems/maximal-rectangle/?utm_source=LCUS&utm_medium=ip_redirect&utm_campaign=transfer2china
     */
    public class MaximalRectangle {
    
        //单调栈的方式
        public static int maximalRectangle(char[][] matrix) {
            //边界判断
            if(matrix == null || matrix.length == 0 || matrix[0].length == 0)
                return 0;
    
            //分析题 组成1的最大子矩形 其中有多少个1  那么我们可以遍历每一行 最大矩阵的底部总是会落在某一行上
            //接着我们定义一个长度为其map的列的数组 存放每一行的列值情况 如果map对应的每一行位置是‘0’ 那么就是对应赋值0 如果是‘1’ 那就累加上上一行同列的1情况
            //表示这一列 有多少行是1 可以构成矩形的
            int[] height = new int[matrix[0].length];    //定义数组存放每一列的 作为底部，往上有多少个1
            int maxArea = 0;                          //定义矩形大小值 也就是对应有多少个1
    
            //遍历整个矩形
            for(int i = 0; i < matrix.length; i++){
                for (int j = 0; j < matrix[0].length; j++){
                    //给数组赋值 第一行 i=0  对于该行每一列 0 则给height数组赋值0   1 就赋值1
                    // 第二行 i=1  每一列接着覆盖height数组  如果当前是0 那就直接覆盖为0 表示是无法构成矩形的 如果是1 那么就累加起上一行对于同列位置的值 如果上一行是1 那这一行就为2 表示高度有2 以此类推得到每一行做底部矩形的情况
                    height[j] = matrix[i][j] == '0' ? 0 : height[j] + 1;
                }
                //刷新完当前i行 对应作为矩形底部的 值  就开始进行 单调栈的处理逻辑 从小到大排列 调用对应的函数 传入height数组 得到以当前i行做底部的最大全1的矩形
                maxArea = Math.max(maxArea, getArea2(height));
    
            }
            return maxArea;
        }
    
        //以当前行 作为矩形底部 计算最大全1矩形  单调栈
        public static int getArea(int[] height){
            //边界判断
            if(height == null || height.length == 0) return 0;
    
            Stack<Integer> stack = new Stack<>();     //定义栈结构 从小到大
            int n = height.length;                     //数组长度
            int maxArea = 0;                           //定义每一列最最小值高度时 矩形面积的最大1的个数
            for(int i = 0; i < n; i++){
                while (!stack.isEmpty() && height[stack.peek()] >= height[i]){
                    //栈非空 且栈顶值 大于等于 当前值  弹出栈顶 计算以栈顶该值为最小高度的矩形面积
                    int pop = stack.pop();    //弹出的栈值s索引 表示矩形高度
                    int widthIndex = stack.isEmpty() ? -1 : stack.peek();   //左侧边界 如果弹出后栈空 说明左边 也就是前面的值都是大于其高度的 索引直接赋值-1 否则 那么当前栈顶位置就是边界 并且不能包含 值是小于弹出的值的
                    //刷新当前pop最小高度值的矩形 宽度的边界 (widthIndex,i) 两边都是不包含的 开区间
                    maxArea = Math.max(maxArea, (i - widthIndex - 1)*height[pop]);
                }
                //栈空 大于栈顶值 直接入栈
                stack.push(i);
            }
            //栈最后非空 需要继续处理 说明栈中的值 在往后的位置没有比他们小的值 所以所在矩阵有边界能到数组最后一个元素
            while(!stack.isEmpty()){
                int pop = stack.pop();    //弹出的栈值s索引 表示矩形高度
                int widthIndex = stack.isEmpty() ? -1 : stack.peek();   //左侧边界 如果弹出后栈空 说明左边 也就是前面的值都是大于其高度的 索引直接赋值-1 否则 那么当前栈顶位置就是边界 并且不能包含 值是小于弹出的值的
                //刷新当前pop最小高度值的矩形 宽度的边界 (height.length,i) 两边都是不包含的 开区间
                maxArea = Math.max(maxArea, (height.length - widthIndex - 1)*height[pop]);
            }
            return maxArea;
        }
    
        //以当前行 作为矩形底部 计算最大全1矩形  手写数组单调栈 效率更高
        public static int getArea2(int[] height){
            //边界判断
            if(height == null || height.length == 0) return 0;
    
    
            int n = height.length;                     //数组长度
            int[] stack = new int[n];     //定义栈结构 从小到大
            int stackIndex = -1;          //数组起始索引 一开始没有元素 所以赋值-1
            int maxArea = 0;                           //定义每一列最最小值高度时 矩形面积的最大1的个数
            for(int i = 0; i < n; i++){
                while (stackIndex != -1 && height[stack[stackIndex]] >= height[i]){
                    //栈非空 且栈顶值 大于等于 当前值  弹出栈顶 计算以栈顶该值为最小高度的矩形面积
                    int pop = stack[stackIndex--];    //弹出的栈值s索引 表示矩形高度 注意同时要索引--
                    int widthIndex = stackIndex == -1 ? -1 : stack[stackIndex];   //左侧边界 如果弹出后栈空 说明左边 也就是前面的值都是大于其高度的 索引直接赋值-1 否则 那么当前栈顶位置就是边界 并且不能包含 值是小于弹出的值的
                    //刷新当前pop最小高度值的矩形 宽度的边界 (widthIndex,i) 两边都是不包含的 开区间
                    maxArea = Math.max(maxArea, (i - widthIndex - 1)*height[pop]);
                }
                //栈空 大于栈顶值 直接入栈 注意起始索引是-1  所以来到下个值赋值 需先++
                stack[++stackIndex] = i;
            }
            //栈最后非空 需要继续处理 说明栈中的值 在往后的位置没有比他们小的值 所以所在矩阵有边界能到数组最后一个元素
            while(stackIndex != -1){
                int pop = stack[stackIndex--];    //弹出的栈值s索引 表示矩形高度 索引同步需要--
                int widthIndex = stackIndex == -1 ? -1 : stack[stackIndex];   //左侧边界 如果弹出后栈空 说明左边 也就是前面的值都是大于其高度的 索引直接赋值-1 否则 那么当前栈顶位置就是边界 并且不能包含 值是小于弹出的值的
                //刷新当前pop最小高度值的矩形 宽度的边界 (height.length,i) 两边都是不包含的 开区间
                maxArea = Math.max(maxArea, (height.length - widthIndex - 1)*height[pop]);
            }
            return maxArea;
        }
    }

### 六、题目四 ###

### 给定一个二维数组matrix，其中的值不是0就是1， ###

### 返回全部由1组成的子矩形数量 ###

package class25;
    
    /**
     * 给定一个二维数组matrix，其中的值不是0就是1，
     * 返回全部由1组成的子矩形数量
     * <p>
     * https://leetcode.cn/problems/count-submatrices-with-all-ones/
     */
    public class CountSubmatricesWithAllOnes {
    
        //方法： 单调栈技巧
        public int numSubmat(int[][] mat) {
            //边界判断
            if (mat == null || mat.length == 0 || mat[0].length == 0) return 0;
    
            //分析题意 组成1的子矩形数量 我们就按每一行 从上到下 每一行作为一个矩形底部
            //然后分别去计算 第0行做底部 有多少个子矩形  第1行做底部 有多少个子矩形...
            //最后在每次累加起来
    
            //定义一个变量 保存全部的子矩形数量
            int num = 0;
            //定义一个数组 长度对应mat的列数，分别存放每一行时刻的 1 的情况
            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的1值高度 如果当前行 所在列为0  那么就直接赋值0 表示没有高度
                    // 如果非0 当前列值是 1  有高度  刷新则把前面时刻的值height[j] + 1
                    height[j] = mat[i][j] == 0 ? 0 : height[j] + 1;
                }
                //将当前行的高度数组 传入函数调用返回以当前i行做矩阵底部 有多少个全1 子矩形数量 累加到num
                num += getCounts(height);
            }
            return num;
        }
    
    
        // 比如
        //              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
        //同样 2） 求高度5的 跟6的数量是一样的  所以数量最终是 (6-4) * 21
        // 这就是任何一个数字从栈里弹出的时候，计算矩形数量的方式
        public static int getCounts(int[] height) {
            //定义手写 数组栈结构 长度等长 height
            int[] stack = new int[height.length];
            //起始索引 赋值-1 一开始没有元素
            int stackIndex = -1;
            //定义一个结果集 数量
            int num = 0;
    
            //开始遍历 当前行 做矩形底部的高度数组  单调栈处理 从小到大
            for (int i = 0; i < height.length; i++) {
                while (stackIndex != -1 && height[stack[stackIndex]] >= height[i]) {
                    //栈非空 且当前栈顶大于等于 当前i值 弹出该栈顶的高度 计算其子矩形数量
                    int pop = stack[stackIndex--];
    
                    //注意 如果出现有重复高度值 也就是相等的情况下 pop弹出后 不计算直接跳过
                    //因为等到后面最后的一个相同高度的位置 由最后一个位置 计算这个高度的全部子矩形 避免重复
                    if (height[pop] > height[i]) {
                        //判断以pop高度的区间 左边边界到哪 如果弹出后 栈空了 说明左侧没有比其小的，左边界就是-1 右边界就是当前i  两边都是开区间 不包含
                        int left = stackIndex == -1 ? -1 : stack[stackIndex];
                        int n = i - left - 1;     //counts就是将边界中间的个数计算出来 得到矩形的宽度
    
                        //注意这里 为了避免计算重复子矩形  我们在前面分析的结论 在pop高度下 个数有 n*(n+1)/2 个
                        //然后高度可以依次-1  但是要考虑要大于 左右边界的高度的较大值。 小于等于的高度，就等到后面来到边界位置 在一起清算矩形 避免重复
                        //所以个数就是 （高度pop - 两边较大值高度）   *   n*(n+1)/2
    
                        //取出两边界的较大值 left如果是-1 越界位置 就表示左侧都是符合的范围 高度就默认是0  否则就是对应的高度值，
                        int down = Math.max(left == -1 ? 0 : height[left], height[i]);
                        num += (height[pop] - down) * count(n);
                    }
                }
                //栈空 或者i值大于当前栈顶 直接入栈
                stack[++stackIndex] = i;
            }
    
            //最后栈中还有元素 就继续进行结算
            //栈中没弹出 说明其右侧 的值 都是大于自己的高度 所以矩形右侧边界就能来到数组最后一个位置
            while(stackIndex !=-1)
            {
                //栈非空 且当前栈顶大于等于 当前i值 弹出该栈顶的高度 计算其子矩形数量
                int pop = stack[stackIndex--];
                //判断以pop高度的区间 左边边界到哪 如果弹出后 栈空了 说明左侧没有比其小的，左边界就是-1 右边界就是数组长度  两边都是开区间 不包含
                int left = stackIndex == -1 ? -1 : stack[stackIndex];
                int n = height.length - left - 1;     //counts就是将边界中间的个数计算出来 得到矩形的宽度
    
                //注意这里 为了避免计算重复子矩形  我们在前面分析的结论 在pop高度下 个数有 n*(n+1)/2 个
                //然后高度可以依次-1  但是要考虑要大于 左右边界的高度的较大值。 小于等于的高度，就等到后面来到边界位置 在一起清算矩形 避免重复
                //所以个数就是 （高度pop - 两边较大值高度）   *   n*(n+1)/2
    
                //取出两边界的较大值 left如果是-1 越界位置 就表示左侧都是符合的范围 高度就默认是0  否则就是对应的高度值
                //因为右侧都是符合的 所以就是赋值0 0就不用进行比较了 最小的 所以直接判断左边界即可
                int down = left == -1 ? 0 : height[left];
                num += (height[pop] - down) * count(n);
            }
            return num;
        }
    
    
    
        //计算一个高度 一个矩形范围有多少个子矩形
        public static int count(int n) {
            return (n * (n + 1)) >> 1;
        }
    }

### 七、题目五 ###

### 给定一个数组arr， ###

### 返回所有子数组最小值的累加和 ###

package class26;
    
    /**给定一个数组arr，
     返回所有子数组最小值的累加和
    
     * // 测试链接：https://leetcode.cn/problems/sum-of-subarray-minimums/description/
     * 给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。
     *
     * 由于答案可能很大，因此 返回答案模 10^9 + 7 。
     *
     * // subArrayMinSum1是暴力解
     * // subArrayMinSum2是最优解的思路
     * // sumSubarrayMins是最优解思路下的单调栈优化
     * // Leetcode上不要提交subArrayMinSum1、subArrayMinSum2方法，因为没有考虑取摸
     * // Leetcode上只提交sumSubarrayMins方法，时间复杂度O(N)，可以直接通过
     */
    public class SumOfSubarrayMinimums {
    
    
        //方法：利用单调栈技巧
        public static int sumSubarrayMins(int[] arr) {
            int n = arr.length;                 //数组的长度
            int[] stack = new int[n];           //定义一个数组栈 从小到大排序
    
            //返回一个left[]数组 表示原数组每个位置 i  对应的左边离得最近的 小于等于arr[i] 的位置 就是left[i]
            //利用手写数组栈 单调栈技巧优化 处理出每个位置的对应左边界
            int[] left = nearLessEqualLeft(arr,stack);
            //同理返回right[]数组 每个位置对应右边离得最近的 小于当前位置的有边界索引  stack前面会清空 可以重复利用
            int[] right = nearLessRight(arr,stack);
    
            //得到了以每个位置做最小值的左右边界后  我们再分析
            //假如  左边界索引是 left   当前i位置是最小值   有边界索引是right  两个边界是不包含在内的 我们定义的是不包含边界 避免出现重复
            //所以left,i  这里left是无效位置  所以i前面 左边的个数是left-i个包含i  i,right right无效 所以i后面 右边的个数是right-i 包含i
            //取出该区间内 i作为小值的子数组有多少个 得到个数 再乘以i 就得到了i最小值的全部子数组累加和 其他位置同样遍历得到 累加就得到结果
            //怎么判断多少个？  每个区间肯定需要包含i ，区间内肯定其他位置都是大于i的值的 除非只有自己一个值 所有就有：
            //[left + 1,i],[left+1,i+1]....[left+1,right-1] 这里是以左边第一个有效位置做起点的全部子数组 右边界肯定至少从i开始往右  一共有right-i个
            //[left + 2,i],[left+2,i+1]....[left+2,right-1]  左边第二个有效位置起点的全部子数组 也是right-i个
            //每个子数组的起点就是从[left+1,i]   终点是到right-1   ,一共有 i - left个起点 每个起点根据前面分析 都是能得到right-i个子数组
            //所有全部子数组就是（i-left） * (right-i) 个子数组 再乘以 i 值 就得到了 一个i最小值全部子数组累加和
    
            long res = 0;    //定义一个结果累加和值  题目提到结果可能很大 用long类型
            //开始遍历每个值 得到以每个值做最小值的全部子数组 再乘以值 累加得到结果
            for(int i = 0; i < n; i++){
                long start = i - left[i];  //当前i位置  求其做最小值 区间的起点个数
                long end = right[i] - i;   //同理 终点个数
                res += start*end* (long) arr[i];  //i最小值 乘以 对应的子数组个数 起点*终点 得到最小值的全部累加和   每次i累加到最后
                res %= 1000000007;   //根据题意 结果需要模值
            }
            return (int) res;
        }
    
        //返回一个left[]数组 表示原数组每个位置 i  对应的左边离得最近的 小于等于arr[i] 的位置 就是left[i]
        //利用手写数组栈 单调栈技巧优化 处理出每个位置的对应左边界
        public static int[] nearLessEqualLeft(int[] arr, int[] stack){
            int n = arr.length; //数组长度
            int size = 0;       //栈初始值大小0 还没有数入栈
            int[] left = new int[n];   //定义结果数组 返回
            //遍历数组 我们要求的是每个位置的最接近左侧值 那么就需要从右边开始往左
            for(int i = n-1; i >= 0 ; i--){
                while(size != 0 && arr[stack[size-1]] >= arr[i]){
                    //刷新栈，栈是从右往左入，下一个入就是他的左侧 如果大于的 继续入栈 如果是出现左侧小于等于的值 那么就弹出栈顶 左侧最近且小于等于的值位置就找到了
                    //同时size要先-- 才能表示下标索引
                    left[stack[--size]] = i;   //i位置值小于等于 栈顶 那么栈顶位置的左边界就是i位置
                }
                //栈空 i值左侧值大于右侧栈顶值 直接继续入栈
                stack[size++] = i;
            }
            //栈还有值，继续弹出赋值 说明左侧没有小于等于的值 那么左边界值就赋值-1
            while (size != 0){
                left[stack[--size]] = -1;
            }
            return left;
        }
    
        //返回一个right[]数组 表示原数组每个位置 i  对应的右边离得最近的 小arr[i] 的位置 就是right[i]
        //利用手写数组栈 单调栈技巧优化  处理出每个位置的对应左边界
        public static int[] nearLessRight(int[] arr, int[] stack){
            int n = arr.length; //数组长度
            int size = 0;       //栈初始值大小0 还没有数入栈
            int[] right = new int[n];   //定义结果数组 返回
            //遍历数组  我们要求的是每个位置的最接近的右侧值 所以就需要从左往右
            for(int i = 0; i < n ; i++){
                while (size != 0 && arr[stack[size-1]] > arr[i]){
                    //栈非空 表示从左到右入栈了  那么后面右侧的值i位置 如果小于当前栈顶 那么就表示栈顶位置找到右侧边界  弹出处理
                    //同时size要先-- 才能表示下标索引
                    right[stack[--size]] = i;
                }
                //栈空 或者 栈顶值 小于等于 当前i值也就是右侧值 那么就直接入栈
                stack[size++] = i;
            }
    
            //最后栈中如果还有值  说明右侧没有小于栈中的值 那么表示右侧边界是来到数组长度 n位置 越界位置
            while (size != 0){
                right[stack[--size]] = n;   //依次取出栈顶位置 右侧值赋值 n 同时size要先--
            }
            return right;
        }
    
    
        public static int subArrayMinSum1(int[] arr) {
            int ans = 0;
            for (int i = 0; i < arr.length; i++) {
                for (int j = i; j < arr.length; j++) {
                    int min = arr[i];
                    for (int k = i + 1; k <= j; k++) {
                        min = Math.min(min, arr[k]);
                    }
                    ans += min;
                }
            }
            return ans;
        }
    
        // 没有用单调栈
        public static int subArrayMinSum2(int[] arr) {
            // left[i] = x : arr[i]左边，离arr[i]最近，<=arr[i]，位置在x
            int[] left = leftNearLessEqual2(arr);
            // right[i] = y : arr[i]右边，离arr[i]最近，< arr[i],的数，位置在y
            int[] right = rightNearLess2(arr);
            int ans = 0;
            for (int i = 0; i < arr.length; i++) {
                int start = i - left[i];
                int end = right[i] - i;
                ans += start * end * arr[i];
            }
            return ans;
        }
    
        public static int[] leftNearLessEqual2(int[] arr) {
            int N = arr.length;
            int[] left = new int[N];
            for (int i = 0; i < N; i++) {
                int ans = -1;
                for (int j = i - 1; j >= 0; j--) {
                    if (arr[j] <= arr[i]) {
                        ans = j;
                        break;
                    }
                }
                left[i] = ans;
            }
            return left;
        }
    
        public static int[] rightNearLess2(int[] arr) {
            int N = arr.length;
            int[] right = new int[N];
            for (int i = 0; i < N; i++) {
                int ans = N;
                for (int j = i + 1; j < N; j++) {
                    if (arr[i] > arr[j]) {
                        ans = j;
                        break;
                    }
                }
                right[i] = ans;
            }
            return right;
        }
    
    
        public static int[] randomArray(int len, int maxValue) {
            int[] ans = new int[len];
            for (int i = 0; i < len; i++) {
                ans[i] = (int) (Math.random() * maxValue) + 1;
            }
            return ans;
        }
    
        public 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 maxLen = 100;
            int maxValue = 50;
            int testTime = 100000;
            System.out.println("测试开始");
            for (int i = 0; i < testTime; i++) {
                int len = (int) (Math.random() * maxLen);
                int[] arr = randomArray(len, maxValue);
                int ans1 = subArrayMinSum1(arr);
                int ans2 = subArrayMinSum2(arr);
                int ans3 = sumSubarrayMins(arr);
                if (ans1 != ans2 || ans1 != ans3) {
                    printArray(arr);
                    System.out.println(ans1);
                    System.out.println(ans2);
                    System.out.println(ans3);
                    System.out.println("出错了！");
                    break;
                }
            }
            System.out.println("测试结束");
        }
    
    }