算法 — — 单调栈技巧及常见考题

妖狐艹你老母 2024-04-03 09:38 9阅读 0赞

## 算法 — — 单调栈技巧 ##

### 1 单调栈定义 ###

![在这里插入图片描述][f4baab9d8e37445db3c6914ad2bc6500.png]

### 2 单调栈的实现及算法题目 ###

#### 2.1 单调栈的实现 ####

> 单调栈：从栈底到栈顶，值的大小是由小到大

##### 2.1.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){
        
        //存储每个位置对应结果【i位置的左边比arr[i]小的值，右边比arr[i]小的值，只存下标】
        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 j = stack.pop();
                //左边比i位置小的值的下标[如果栈不为空，就取栈顶值，也就是之前i位置压得值]
                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;//右边没有比其更小得值了，因此全部为-1
        }
        return res;
    }

##### 2.1.2 有重复值的单调栈实现 #####

//有重复值：使用链表串起来
    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 {
        
                //栈为空或值不等，则新建链表
                List<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;
    }

#### 2.2 正数数组arr中子数组sub中(sub累加和\*sub最小值)，求最大值 ####

> LeetCode 1856 - Maximum Subarray Min-Product  
> https://leetcode.com/problems/maximum-subarray-min-product/

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

// 注意溢出的处理即可，也就是用long类型来表示累加和
    // 还有优化就是，你可以用自己手写的数组栈，来替代系统实现的栈，也会快很多
    public int maxSumMinProduct(int[] arr){
        
        int size = arr.length;
        long[] sums = new long[size];
        //[i..j]位置，累加和->前缀和数组
        //sub子数组的和 * sub子数组中最小值
        //前缀和数组
        sums[0] = arr[0];
        for(int i = 1; i < size; i++){
        
            sums[i] = sums[i-1] + arr[i];
        }
        long max = Long.MIN_VALUE;
        //错化处理，算错就算错，最后有正确答案覆盖错误的
        Stack<Integer> stack = new Stack<>();
        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 (int) (max % 1000000007);
    }

手动改写栈：

// 注意测试题目数量大，要取模，但是思路和课上讲的是完全一样的
    // 注意溢出的处理即可，也就是用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);
    }

#### 2.3 最大矩形面积 ####

> LeetCode - 84. Largest Rectangle in Histogram  
> https://leetcode.com/problems/largest-rectangle-in-histogram/submissions/

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

class Solution {
        
        public int largestRectangleArea(int[] heights) {
        
            if(heights == null || heights.length == 0){
        
                return 0;
            }
            int maxArea = 0;
            Stack<Integer> stack = new Stack<>();
            for(int i = 0; i < heights.length; i++){
        
                while(!stack.isEmpty() && heights[stack.peek()] >= heights[i]){
        
                    //以heights[j]为高
                    int j = stack.pop();
                    //找到矩形左边界
                    int k = stack.isEmpty() ? -1 : stack.peek();
                    maxArea = Math.max(maxArea, (i - k - 1) * heights[j]);
                }
                stack.push(i);
            }
            while(!stack.isEmpty()){
        
                int j = stack.pop();
                int k = stack.isEmpty() ? -1 : stack.peek();
                maxArea = Math.max(maxArea, (heights.length - k - 1) * heights[j]);
            }
            return maxArea;
        }
    }

#### 2.4 二维数组，最大子矩形，内部1的个数 ####

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

> LeetCode - 85. Maximal Rectangle  
> https://leetcode.com/problems/maximal-rectangle/

class Solution {
        
        public int maximalRectangle(char[][] matrix) {
        
            if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
        
                return 0;
            }
            //压缩数组
            int maxArea = 0;
            int[] height = new int[matrix[0].length];
            for(int i = 0; i < matrix.length; i++){
        
                for(int j = 0; j < matrix[0].length; j++){
        
                    height[j] = matrix[i][j] == '0' ? 0 : height[j] + 1;
                }
                maxArea = Math.max(maxArea, maxRecFromBottom(height));
            }
            return maxArea;
        }
        
        //height是正方图数组[单调栈]
        public int maxRecFromBottom(int[] height){
        
            if(height == null || height.length == 0){
        
                return 0;
            }
            int maxArea = 0;
            Stack<Integer> stack = new Stack<>();
            for(int i = 0; i < height.length; i++){
        
                while(!stack.isEmpty() && height[stack.peek()] >= height[i]){
        
                    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;
        }
    }

#### 2.5 二维数组，全部由1组成的子矩阵数量 ####

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

> LeetCode - 1504. Count Submatrices With All Ones  
> https://leetcode.com/problems/count-submatrices-with-all-ones/

// 比如
    	//              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
    	// 这就是任何一个数字从栈里弹出的时候，计算矩形数量的方式
    class Solution {
        
        public int numSubmat(int[][] mat) {
        
            if(mat == null || mat.length == 0 || mat[0].length == 0){
        
                return 0;
            }
            int[] height = new int[mat[0].length];//以每一行做底
            int nums = 0;
            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;
        }
        
        public 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];//peek
                        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;//push
            }
            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 int num(int n){
        
            return ((n * (n + 1)) >> 1);
        }
    }

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

给定一个数组arr，  
返回所有子数组最小值的累加和

> LeetCode - 907. Sum of Subarray Minimums  
> https://leetcode.com/problems/sum-of-subarray-minimums/

class Solution {
        
        //用数组实现栈
        public static int sumSubarrayMins(int[] arr) {
        
    		int[] stack = new int[arr.length];
    		int[] left = nearLessLeft(arr, stack);
    		int[] right = nearLessEqualRight(arr, stack);
    		long ans = 0;
    		for (int i = 0; i < arr.length; i++) {
        
    			long start = i - left[i];
    			long end = right[i] - i;
    			ans += start * end * (long) arr[i];
    			ans %= 1000000007;
    		}
    		return (int) ans;
    	}
        
    
        //小于等于右边的范围【每个位置，以arr[i]做最小值的子数组】
        //right[i] = x : arr[i]右边，离arr[i]最近，<=arr[i]的数，位置在x
    	public static int[] nearLessEqualRight(int[] arr, int[] stack) {
        
    		int N = arr.length;
    		int[] right = new int[N];
    		int size = 0;
    		for (int i = N - 1; i >= 0; i--) {
        
    			while (size != 0 && arr[i] <= arr[stack[size - 1]]) {
        
    				right[stack[--size]] = i;
    			}
    			stack[size++] = i;
    		}
    		while (size != 0) {
        
    			right[stack[--size]] = -1;
    		}
    		return right;
    	}
    
        //小于左边的范围
        //left[i] = x : arr[i]左边，离arr[i]最近，<arr[i]的数，位置在x
    	public static int[] nearLessLeft(int[] arr, int[] stack) {
        
    		int N = arr.length;
    		int[] left = new int[N];
    		int size = 0;
    		for (int i = 0; i < N; i++) {
        
    			while (size != 0 && arr[i] < arr[stack[size - 1]]) {
        
    				left[stack[--size]] = i;
    			}
    			stack[size++] = i;
    		}
    		while (size != 0) {
        
    			left[stack[--size]] = N;
    		}
    		return left;
    	}
    
    }

> 要有以确定某个元素，然后找目标的思想。  
> 例如：找寻子数组，那么可以转化成以arr中的某个元素为起点，包含该元素的子数组有多少

[f4baab9d8e37445db3c6914ad2bc6500.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/66e04527e5fe4a34bc769372c4320f41.png