Algorithm Prototype: Monotone Stack

what is monotone stack?

What is monotone stack

A monotonic stack is a stack whose elements are monotonically increasing or decreasing.

some times we store the index of element in the stack because in this way we can track more information.

Prototype

We can use monotonic stack to achieve this goal: for each element in array, find its left & right, the closest element smaller or bigger than it.

for example, given a array [1,3,2,2,4,5,1], for the element 4, its left & right closest smaller element is 2 & 1

// for each element in arr, find its left & right
// closest element smaller than it 
// assume there is no repeated element in the array
public int[][] findClosestSmallerElement(int[] arr) {
    // prepare a stack
    // iterate array, check if the stack top is smaller than element or not
    // if it's smaller, then push the element into stack
    // if it's bigger, then pop out the stack top, resolve this element, its left closest element is the element under it in stack, its right cloest element is current element
    // recurse above steps until current element is bigger than stack top
    Stack<Integer> stack = new Stack<>();
    
    int[][] res = new int[arr.length][2];
    int tempIndex;
    for(int i = 0; i < arr.length; i++) {
        while(!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
            // current element is smaller than stack top
            tempIndex = stack.pop();
            res[tempIndex][1] = i;
            if (!stack.isEmpty()) {
                res[tempIndex][0] = stack.peek();
            } else {
                res[tempIndex][0] = -1;
            }
        }
        stack.push(i);
    }
    
    // the rest element in stack don't have right smaller elements
    while(!stack.isEmpty()) {
        tempIndex = stack.pop();
        res[tempIndex][1] = -1;
        if (!stack.isEmpty()) {
            res[tempIndex][0] = stack.peek();
        } else {
            res[tempIndex][0] = -1;
        }
    }
}

Challenge 1

Given arr, only contains positive integer, any sub array could have the value: sum * min, get the biggest value of this formular from all sub array

We encounter the issue of counting all sub arrays, so we can transform the problem as: based each element, what’s the biggest value of that formular.

in this specific problem, we can see, take each element as the min value in array, what’s the biggest value of the formular

public int getBiggestFormular(int[] arr) {
    // first, pre-compute a sum array
    // iterate the array, for each element
    // find the its left&right, closest smaller element index
    // if there is no smaller, then all element between the boundary and this element is valid
    // calculate the formular
    int[] sumArr = new int[arr.length];
    int sum = 0;
    for(int i = 0; i < arr.length; i++) {
        sum += arr[i];
        sumArr[i] = sum;
    }
    
    int[][] minIndex = new int[arr.length][2];
    int tempIndex;
    Stack<Integer> stack = new Stack<>();
    // when current element is smaller than stack top, resolve stack top element.
    for(int i = 0; i < arr.length; i++) {
        while(!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
            tempIndex = stack.pop();
            minIndex[tempIndex][1] = i;
            minIndex[tempIndex][0] = stack.isEmpty() ? -1 : stack.peek();
        }
        stack.push(i);
    }
    
    while(!stack.isEmpty()) {
        tempIndex = stack.pop();
        minIndex[tempIndex][1] = -1;
        minIndex[tempIndex][0] = stack.isEmpty() ? -1 : stack.peek();
    }
    
    int max = 0;
    int left, right;
    for(int i = 0; i < arr.length; i++) {
        left = Math.max(0, arr[i][0] + 1);
        right = Math.min(arr.length - 1, arr[i][1] - 1);
        max = Math.max(max, (sumArr[right] - sumArr[left] + arr[left]) * arr[i] );
    }
    
    return max;
}

Retro

• when calculate the sum of each sub array, we can pre-calculate accumulating array, then it’s easier to get the sum of each sub array
• when encountering the problem involving all sub array, usually it can be transferred to based on each element, what’s the value of that sub array.