Monotone stack problem solving

1. Monotone stack structure

Niu Ke link

Method: Monotone stack

algorithm

Maintaining a monotonic incremental stack, you can find elements smaller than the current element
Convention: Current element cur, top of stack, tempTop of stack

• Traversing array
• If the current element is larger than the top element of the stack, it is stacked (the index of the stack element, not the value)
• Otherwise, the top of the stack element will be out of the stack. At this time, the closest to the left of tempTop and the value smaller than tempTop is the current top of the stack element, and the closest to the right of tempTop and the value smaller than tempTop is the current element cur. Then the process is cycled until the second step condition is satisfied.
• After traversing the array, the elements in the stack are output according to the above rules.

    private static void leftRightWay(int[] arr){
        int len = arr.length;
        int[] right = new int[len];
        int[] left = new int[len];
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < len; i++) {
            while(!stack.empty() && arr[i] < arr[stack.peek()]) {
                int tempTop = stack.pop();
                left[tempTop] = stack.empty() ? -1 : stack.peek();
                right[tempTop] = i;
            }
            stack.push(i);
        }

        while(!stack.empty()) {
            int tempTop = stack.pop();
            left[tempTop] = stack.empty() ? -1 : stack.peek();
            right[tempTop] = -1;
        }

        for(int i = 0; i < len; i++) {
            System.out.println(left[i] + " " + right[i]);
        }
    }

Complexity

• Time complexity: O(N), each element is processed twice, and its index is put into and out of the stack.

739. Daily temperature

LeetCode link

Method 1: Dynamic programming. Details can be viewed in the link.

    public int[] dailyTemperatures(int[] T) {
        int len = T.length;
        int[] result = new int[len];
        result[len - 1] = 0;
        for(int i = len - 2; i >= 0; i--) {
            for(int j = i + 1; j < len; j += result[j]) {
                // Focus on j += result[j]
                // If the temperature of the day is lower than that of the day after, the result is 1 directly.
                // If the temperature of the day is higher than that of the day after, then we have to compare [the day higher than that of the day after] the cycle process.
                // If the temperature of the next day is no bigger than that of the next day, then naturally it can't be bigger than that of that day.
                if (T[i] < T[j]) {
                    result[i] = j - i;
                    break;
                } else if (result[j] == 0) {
                    result[i] = 0;
                    break;
                }
            }
        }

        return result;
    }

Method 2: Monotone stack

algorithm

Maintain a monotonically decreasing stack, where elements are indexed

• Traversing array
• If the current element is less than the top element of the stack, it is stacked
• Otherwise, the top element of the stack will be out of the stack, and the current element index - the top element of the stack is the result of the corresponding location.

    public int[] dailyTemperatures(int[] T) {
        int len = T.length;
        int[] result = new int[len];
        Stack<Integer> stack = new Stack();
        for(int i = 0; i < len; i++) {
            while(!stack.empty() && T[i] > T[stack.peek()]) {
                int tempTop = stack.pop();
                result[tempTop] = i - tempTop;
            }
            stack.push(i);
        }

        while(!stack.empty()) {
            result[stack.pop()] = 0;
        }

        return result;
    }