The introduction

This article will introduce what is monotone stack, monotone stack used to solve what problems, and its flexible use in the algorithm body, to help you quickly solve similar problems, algorithm learning is thinking, do not memorize code flow.

The stack structure:

A fifo data structure, similar to a bucket, with only one exit, first in and last out.

Monotonous stack:

Monotone stack is to ensure that the elements in the stack increase monotonically according to some rule, or monotone decrease, note that the value of the elements in the stack is not monotone.

Example: arr =,2,5,4,7,8 [3] arr =,2,5,4,7,8 [3] arr =,2,5,4,7,8 [3], increasing subsequence is:,5,7,8 [3],5,7,8 [3],5,7,8 [3], increasing deposited in the stack is value index: ,2,4,5 stack = [0] stack = stack,2,4,5 [0] = [0,2,4,5]

Solve what problem?

Given an array arr =,1,4,5,3,7 [3] arr =,1,4,5,3,7 [3] arr =,1,4,5,3,7 [3]

• In order to
  $a = arr[i]$Location,
  $arr[l] < a , a > arr[r]$,
  $l,r$The nearest location of.
  • A =4a =4a =4, the closest element on the left less than 4 is 1, and the closest element on the right less than 4 is 3.

• A =arr[I]a=arr[I]a=arr[I] position, ARr [L]> A,a
  
  a,a
  
  a,a
  
  a,a
  
  a, A
  
  a, A
  [r]arr[r]>
  [r]arr[r]>
  [r]arr[l]>
  [r]arr[l]>
  [r]arr[l]>

Violence:

• Each position to the left, each position to the right, the time is O(N)O(N)O(N) O(N), the total time is O(N2)O(N^2)O(N2).

Monotonous stack:

• Monotone stack: time complexity O(N)O(N)O(N) O(N), space complexity O(N)O(N)O(N) O(N)

Find an array interval boundary

1. Find small boundaries

Given an array arrarrarr, find the positions on the left and right that are smaller than and closest to this number. If you want to find such information for each number, can the overall cost reach O(N)O(N)O(N) O(N)?

Example:

• 
  $Arr =,1,4,5,2,7 [3]$
• Returns: [[- 1, 1], [, – 1-1], [1, 4], [2, 4], [1-1], [4-1]] [[1, 1], [1, 1], [1, 4], [2, 4], [1, 1], [4, 1]] [[- 1, 1], [, – 1-1], [1, 4], [2, 4], [1, – 1], [4-1]]

Violent solution:

• Go through the number group, each position iii, and find the first value on the left and the first value on the right of [0, I −1][0, I-1][0, I −1] and [I +1,n−1] and [I +1, n-1].
• The complexity of traversing the number group is O(N)O(N)O(N) O(N)O(N)O(N) O(N^2)O(N2) O(N^2)O(N2)

public static int[][] violenceMethod(int[] arr) {
    if (arr == null || arr.length == 0) return null;
    int n = arr.length;
    int[][] ans = new int[n][2];
    for (int i = 0; i < n; i++) {
        int leftIndex = -1, rightIndex = -1;
        for (int l = i - 1; l >= 0; l--) {
            if (arr[l] < arr[i]){
                leftIndex = l;
                break; }}for (int r = i + 1; r < n; r++) {
            if (arr[r] < arr[i]){
                rightIndex = r;
                break;
            }
        }
        ans[i][0] = leftIndex;
        ans[i][1] = rightIndex;
    }
    return ans;
}
Copy the code

Monotone stack solution:

• The stack holds the index of the array, and the value of the index increases monotonically.
• When the element to be added is smaller than the corresponding element at the top of the stack, the settlement of the elements in the stack begins, and the left and right boundaries of the settlement of the elements at the top of the stack pop up. Push iii onto the stack until the current position arr[I]> ARr [stack.peek()] ARr [I]>arr[stack.peek()]arr[I]>arr[stack.peek()].
• Once you’re done traversing the array for the last time, you need to settle the stack elements.
• Event complexity O(N)O(N)O(N), space complexity O(N)O(N)O(N) O(N)

/** * Monotone stack problem: If you want to find a number in an array, the position on the left and right is smaller than the number and closest to the number * If you want to find such information for each number, can the overall cost reach O(n)? Arr = [3,1,4,5,3,7] * 
 * The index is stored in the stack, keeping the corresponding value of the index in the stack strictly monotonically increasing. * 2. When an element arr[I] > arr[stack.peek()] is encountered, the stack is pushed. */ arr[I] < arr[stack.peek] < arr[stack.peek] = arr[I] < arr[stack.peek] = arr[I] < arr[stack.peek] = arr[I] < arr[stack.peek]
public static int[][] getNearLessArray(int[] arr) {
    if (arr == null || arr.length == 0) return null;
    int n = arr.length;
    int[][] result = new int[n][2];
    // The index stored in the stack keeps monotonically increasing
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < n; i++) {
        while(! stack.isEmpty() && arr[stack.peek()] > arr[i]) {// If the current element makes it impossible for the stack element to keep increasing monotonously, the stack element is cleared
            int index = stack.pop();
            int preMin = stack.isEmpty() ? -1 : stack.peek();
            result[index][0] = preMin;
            result[index][1] = i;
        }
        // After the settlement, push the current element onto the stack
        stack.add(i);
    }
    There is no element smaller to the right of the stack, otherwise it must have been popped in the previous process
    / / eg: [1, 2, 3, 4, 5]
    while(! stack.isEmpty()) {int index = stack.pop();
        int preMin = stack.isEmpty() ? -1 : stack.peek();
        result[index][0] = preMin;
        result[index][1] = -1;
    }
    return result;
}
Copy the code

2. Find large boundaries

Given an array arrarrarr, find the position on the left and right that is larger than the number and nearest to the number. If you want to find such information for each number, can the overall cost reach O(N)O(N)O(N) O(N)?

Example:

• 
  $Arr =,1,4,5,2,7 [3]$
• Returns: [[- 1, 2], [0, 2], [- 1, 3], [- 1, 4], [3, 5], [- 1-1]] [[1, 2], [0, 2], [- 1, 3], [- 1, 4], [3, 5], [1, 1]] [[- 1, 2], [0, 2], [- 1, 3], [- 1, 4], [3, 5], [ – 1, 1]] –

Monotone stack solution: keep the value of the index in the stack decreasing monotonously by changing only one symbol in the while loop

public static int[][] getNearUpperArray(int[] arr) {
    if (arr == null || arr.length == 0) return null;
    int n = arr.length;
    int[][] result = new int[n][2];
    // The index stored in the stack keeps monotonically increasing
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < n; i++) {
        // Ensure the monotonic decrease
        while(! stack.isEmpty() && arr[stack.peek()] < arr[i]) {// If the current element makes it impossible for the stack element to keep increasing monotonously, the stack element is cleared
            int index = stack.pop();
            int preMin = stack.isEmpty() ? -1 : stack.peek();
            result[index][0] = preMin;
            result[index][1] = i;
        }
        // After the settlement, push the current element onto the stack
        stack.add(i);
    }
    There is no element smaller to the right of the stack, otherwise it must have been popped in the previous process
    / / eg:,6,4,2 [8]
    while(! stack.isEmpty()) {int index = stack.pop();
        int preMin = stack.isEmpty() ? -1 : stack.peek();
        result[index][0] = preMin;
        result[index][1] = -1;
    }
    return result;
}
Copy the code

Practical link

1. Subarray summation and its minimum product problem

Topic: Given an Arrarrarr that only contains positive numbers, any subarray subsubsub in arrarrarR must be able to calculate what sum(sub)∗min(sub)sum(sub) * min(sub)sum(sub)∗min(sub) is, So out of all of the subarrays, what is this maximum?

Violent solution

Analysis of ideas:

• For an array of length NNN, the number of subarrays is the interval [L,r][l,r][L,r] in the two-level for loop.
• Then traverse the interval [L,r][L,r][L, R] to solve the sum of the interval, and find the minimum value of the interval, and then update the answer.
• The time complexity of the two-layer for loop O(N2)O(N^2)O(N2), the time complexity of the solution and minimum of the traversal interval is O(N)O(N)O(N) O(N)O(N ^3)O(N3) O(N3)O(N3)O(N3)

/ * * * violence ideas: first is beginning with each location, [l, r] the son of subarray all situation, a maximum update * 1. Find the interval complexity O(n^2), calculate the summation and determine that the minimum complexity is O(n), and the total complexity is O(n^3) */
public static int maxSubSunMinMax(int[] arr) {
    int n = arr.length;
    int max = Integer.MIN_VALUE;
    for (int l = 0; l < n; l++) {
        for (int r = l; r < n; r++) {
            int min = Integer.MAX_VALUE;
            int sum = 0;
            for (intk = l; k <= r; k++) { sum += arr[k]; min = Math.min(min, arr[k]); } max = Math.max(max, sum * min); }}return max;
}
Copy the code

Monotone stack solution

• Take the minimum value in the interval as a breakthrough point, and think about this problem in a different way.
• Assume position arr[I]arr[I]arr[I]arr[I] as the minimum, the furthest reachable position to the left window, and the furthest reachable position to the right window. The interval ensures that arr[I]arr[I]arr[I] is the minimum value.
• So the problem is, in a monotone stack, find the closest distance to the left that is smaller than you, and the closest distance to the right that is smaller than you.
• Note: Sum (sub)∗min(sub)sum(sub) * min(sub)sum(sub)∗min(sub) * min(sub) Sum (sub)∗min(sub)
• So we iterate through the array, minimizing each location, and finding the maximum range that can be expanded.

This problem also uses pre-processing techniques:

• Interval summation problem, a typical preprocessing array technique. Sum [I]sum[I]sum[I]sum[I] represents the sum of [0, I][0, I].
• So the summation of the interval can be taken directly from the sumsum array.

Complexity calculation:

• Preprocessing summation array, time complexity O(N)O(N)O(N) O(N) space complexity O(N)O(N)O(N) O(N).
• Iterating through the array, each element will only be pushed up and down the stack once at most, so the total time is O(N)O(N)O(N) O(N)
• Time complexity O(N)O(N)O(N) O(N) space complexity O(N)O(N)O(N) O(N) down

/ optimization idea: * * * * 1. The sub accumulation and, with pretreatment techniques. * 2. Interval definition: the maximum answer must be obtained by taking position L as the minimum value of the subarray. Each position is iterated for an answer, and O(n) is taken down. * 3. Equivalent, find the first position on the left of arr[l] is smaller than itself, the first position on the right is smaller than itself, this is not the monotonic stack definition. * 3.eg: arr[3,4,5,6,3,2,7], if 4 is the minimum value, the position on the left smaller than itself is 0, the position on the right smaller than itself is 4 * 4. This determines an interval: [4,5,6], and each position tries to be its own minimum. * /
public static int maxSubSunMinMax1(int[] arr) {
    int n = arr.length;
    //1. Preprocess the array
    int[] sum = new int[n];
    sum[0] = arr[0];
    for (int i = 1; i < n; i++) {
        sum[i] = sum[i - 1] + arr[i];
    }
    //2. Monotone stack solves the farthest distance between the left and right sides smaller than itself, monotone increasing stack
    Stack<Integer> stack = new Stack<>();
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        // This is equivalent to finding leftIndex and rightIndex within the interval
        while(! stack.isEmpty() && arr[stack.peek()] >= arr[i]) {// There is currently an element that cannot be monotonically incremented. The minimum value on the right is rightIndex= I
            int index = stack.pop();// Take the current element as the minimum value
            int subSum = sum[i - 1] - (stack.isEmpty() ? 0 : sum[stack.peek()]);
            max = Math.max(max, subSum * arr[index]);
        }
        stack.add(i);
    }
    //3. Finally settle the remaining elements in the stack
    while(! stack.isEmpty()){int index = stack.pop();
        int subSum = sum[n - 1] - (stack.isEmpty() ? 0 : sum[stack.peek()]);
        max = Math.max(max,subSum * arr[index]);
    }
    return max;
}
Copy the code

2.The largest rectangle in a bar chart

Ideas:

• This is not the height of each column, find the position closest to you on the left, the position closest to you on the right. In the middle is the maximum distance that can be expanded at high energy at the current position.
• Note: in the final settlement, the right margin is -1, that is, there is no value smaller than the right side, otherwise it must be out of the stack, pay attention to the width calculation.

/** * Title: Find the maximum area of a rectangle that can be outlined in a bar chart. * Set each position as the height of the rectangle, find the position on the left that is smaller than you, the position on the right that is smaller than you, and the area in the middle of the rectangle. */
public static int largestRectangleArea(int[] heights) {
    if (heights == null || heights.length == 0) return 0;
    int n = heights.length;
    int maxArea = 0;
    // find the smallest value on the left, the smallest value on the right, increment stack
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < n; i++) {
        while(! stack.isEmpty() && heights[stack.peek()] > heights[i]) {// The current element to be added is smaller than the value corresponding to the top of the stack
            int index = stack.pop();
            int preIndex = stack.isEmpty() ? 0 : stack.peek();
            int width = i - preIndex - 1;
            maxArea = Math.max(maxArea,width * heights[index]);
        }
        stack.add(i);
    }
    // Finally settle the stack element
    while(! stack.isEmpty()){int index = stack.pop();
        int preIndex = stack.isEmpty() ? 0 : stack.peek();
        int width = n - preIndex - 1;
        maxArea = Math.max(maxArea,width * heights[index]);
    }
    return maxArea;
}
Copy the code