02 算法体系班 - 19 单调栈 - 《java笔记》

单调栈结构
单调栈实现
单调栈题目

单调栈结构

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

单调栈实现

public static int[][] getNearLessNoRepeat(int[] arr) {
    int[][] ans = new int[arr.length][2];
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < arr.length; i++) {
        while (!stack.empty() && arr[i] < arr[stack.peek()]) {
            int index = stack.pop();
            ans[index][0] = stack.empty() ? -1 : stack.peek();
            ans[index][1] = i;
        }
        stack.push(i);
    }
    while (!stack.empty()) {
        int index = stack.pop();
        ans[index][0] = stack.empty() ? -1 : stack.peek();
        ans[index][1] = -1;
    }
    return ans;
}


public static int[][] getNearLess(int[] arr) {
    int[][] ans = new int[arr.length][2];
    Stack<LinkedList<Integer>> stack = new Stack<>();
    for (int i = 0; i < arr.length; i++) {
        while (!stack.empty() && arr[i] < arr[stack.peek().peekLast()]) {
            LinkedList<Integer> list = stack.pop();
            int leftIndex = stack.empty() ? -1 : stack.peek().peekLast();
            for (int index : list) {
                ans[index][0] = leftIndex;
                ans[index][1] = i;
            }
        }
        if (!stack.empty() && arr[i] == arr[stack.peek().peekLast()]) {
            stack.peek().offerLast(i);
        } else {
            LinkedList<Integer> list = new LinkedList<>();
            list.offerLast(i);
            stack.push(list);
        }
    }
    while (!stack.empty()) {
        LinkedList<Integer> list = stack.pop();
        int leftIndex = stack.empty() ? -1 : stack.peek().peekLast();
        for (int index : list) {
            ans[index][0] = leftIndex;
            ans[index][1] = -1;
        }
    }
    return ans;
}

单调栈题目

题目1：满足要求的子数组的最大值

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

public static int maxValue2(int[] arr) {
    if (arr == null || arr.length == 0) {
        return Integer.MIN_VALUE;
    }
    int ans = Integer.MIN_VALUE;
    for (int i = 0; i < arr.length; i++) {
        for (int j = i; j < arr.length; j++) {
            int min = Integer.MAX_VALUE;
            int sum = 0;
            for (int k = i; k <= j; k++) {
                min = Math.min(min, arr[k]);
                sum += arr[k];
            }
            ans = Math.max(ans, sum * min);
        }
    }
    return ans;
}


public static int maxValue(int[] arr) {
    if (arr == null || arr.length == 0) {
        return Integer.MIN_VALUE;
    }
    int n = arr.length;
    int[] preSum = new int[n];
    preSum[0] = arr[0];
    for (int i = 1; i < n; i++) {
        preSum[i] = preSum[i - 1] + arr[i];
    }
    return process(arr, preSum);
}
private static int process(int[] arr, int[] preSum) {
    int ans = 0;
    int[] stack = new int[arr.length];
    int cursor = -1;
    for (int i = 0; i < arr.length; i++) {
        while (cursor != -1 && arr[stack[cursor]] >= arr[i]) {
            int index = stack[cursor--];
            int left = cursor == -1 ? -1 : stack[cursor];
            int right = i;
            ans = left == -1 ? Math.max(ans, arr[index] * preSum[right - 1]) : Math.max(ans, arr[index] * (preSum[right - 1] - preSum[left]));
        }
        stack[++cursor] = i;
    }
    while (cursor != -1) {
        int index = stack[cursor--];
        int left = cursor == -1 ? -1 : stack[cursor];
        int right = arr.length;
        ans = left == -1 ? Math.max(ans, arr[index] * preSum[right - 1]) : Math.max(ans, arr[index] * (preSum[right - 1] - preSum[left]));
    }
    return ans;
}

题目2：返回直方图的最大长方形面积

给定一个非负数组arr，代表直方图，返回直方图的最大长方形面积
https://leetcode.com/problems/largest-rectangle-in-histogram


public static int largestRectangleArea(int[] heights) {
    if (heights == null || heights.length == 0) {
        return 0;
    }
    int n = heights.length;
    int[] stack = new int[n];
    int cursor = -1;
    int area = 0;
    for (int i = 0; i < n; i++) {
        while (cursor != -1 && heights[stack[cursor]] >= heights[i]) {
            int index = stack[cursor--];
            int left = cursor == -1 ? -1 : stack[cursor];
            int right = i;
            area = left == -1 ? Math.max(area, heights[index] * right) : Math.max(area, heights[index] * (right - 1 - left));
        }
        stack[++cursor] = i;
    }
    while (cursor != -1) {
        int index = stack[cursor--];
        int left = cursor == -1 ? -1 : stack[cursor];
        int right = n;
        area = left == -1 ? Math.max(area, heights[index] * right) : Math.max(area, heights[index] * (right - 1 - left));
    }
    return area;
}

题目3：全部由1组成的最大子矩形，内部有多少个1

给定一个二维数组matrix，其中的值不是0就是1，返回全部由1组成的最大子矩形，内部有多少个1
https://leetcode.com/problems/maximal-rectangle/submissions/

public static int maximalRectangle(char[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
        return 0;
    }
    int n = matrix.length;
    int m = matrix[0].length;
    int[] height = new int[m];
    int area = 0;
    for (char[] row : matrix) {
        for (int i = 0; i < m; i++) {
            height[i] = row[i] == '0' ? 0 : height[i] + 1;
        }
        area = Math.max(area, largestRectangleArea(height));
    }
    return area;
}

private static int largestRectangleArea(int[] heights) {
    int n = heights.length;
    int[] stack = new int[n];
    int cursor = -1;
    int area = 0;
    for (int i = 0; i < n; i++) {
        while (cursor != -1 && heights[stack[cursor]] >= heights[i]) {
            int index = stack[cursor--];
            int left = cursor == -1 ? -1 : stack[cursor];
            int right = i;
            area = Math.max(area, heights[index] * (right - 1 - left));
        }
        stack[++cursor] = i;
    }
    while (cursor != -1) {
        int index = stack[cursor--];
        int left = cursor == -1 ? -1 : stack[cursor];
        int right = n;
        area = Math.max(area, heights[index] * (right - 1 - left));
    }
    return area;
}

题目4：矩形数量

给定一个二维数组matrix，其中的值不是0就是1，返回全部由1组成的子矩形数量
https://leetcode.com/problems/count-submatrices-with-all-ones/submissions/

public static int numSubmat(int[][] mat) {
    if (mat == null || mat.length == 0 || mat[0] == null || mat.length == 0) {
        return 0;
    }

    int m = mat[0].length;
    int[] heights = new int[m];
    int num = 0;
    for (int[] rows : mat) {
        for (int i = 0; i < m; i++) {
            heights[i] = rows[i] == 0 ? 0 : heights[i] + 1;
        }
        num += rectNum(heights);
    }
    return num;
}

private static int rectNum(int[] height) {
    if (height == null || height.length == 0) {
        return 0;
    }
    int n = height.length;
    int[] stack = new int[n];
    int num = 0;
    int cursor = -1;
    for (int i = 0; i < n; i++) {
        while (cursor != -1 && height[stack[cursor]] >= height[i]) {
            int index = stack[cursor--];

            int left = cursor == -1 ? -1 : stack[cursor];
            int right = i;
            int maxMinIndex = left == -1 ? right : height[left] > height[right] ? left : right;

            num += (height[index] - height[maxMinIndex]) * num(right - left - 1);

        }
        stack[++cursor] = i;
    }
    while (cursor != -1) {
        int index = stack[cursor--];
        int left = cursor == -1 ? -1 : stack[cursor];
        int right = n;
        int maxMinIndex = left == -1 ? -1 : left;
        int down = maxMinIndex == -1 ? 0 : height[left];
        num += (height[index] - down) * num(right - left - 1);
    }
    return num;
}

private static int num(int n) {
    return (n * (n + 1)) >> 1;
}

题目5：所有子数组最小值的累加和

给定一个数组arr，返回所有子数组最小值的累加和
https://leetcode.com/problems/sum-of-subarray-minimums/submissions/

public static int sumSubarrayMins(int[] arr) {
    int n = arr.length;
    int[] stack = new int[n];
    int cursor = -1;
    long sum = 0L;

    for (int i = 0; i < n; i++) {
        while (cursor != -1 && arr[stack[cursor]] >= arr[i]) {
            int index = stack[cursor--];
            int left = cursor == -1 ? -1 : stack[cursor];
            int right = i;

            int num = (index - left) * (right - index);
            sum += (num * (long) arr[index]);
            sum %= 1000000007;
        }
        stack[++cursor] = i;
    }
    while (cursor != -1) {
        int index = stack[cursor--];
        int left = cursor == -1 ? -1 : stack[cursor];
        int right = n;
        int num = (index - left) * (right - index);
        sum += (num * (long) arr[index]);
        sum %= 1000000007;
    }
    return (int) sum;
}