Monotonic Decreasing Stack

A Monotonically Decreasing Stack is a stack where elements are placed in decreasing order from the bottom to the top. Each new element added to the stack must be smaller than or equal to the one below it. If a new element is greater than top of stack then we remove elements from the top of the stack until we find one that is greater or equal to the new element, or until the stack is empty. This ensures that the stack always stays in decreasing order.

Example: 17, 14, 10, 5, 1

How to achieve Monotonic Decreasing Stack?

To achieve a monotonic decreasing stack, you would typically push elements onto the stack while ensuring that the stack maintains a decreasing order from bottom to top. When pushing a new element, you would pop elements from the stack that are greater than the new element until the stack maintains the desired monotonic decreasing property.

To achieve a monotonic decreasing stack, you can follow these step-by-step approaches:

Start with an empty stack.
Iterate through the elements of the input array.
While stack is not empty AND top of stack is less than the current element:
pop element from the stack
Push the current element onto the stack.
After iterating through all the elements, the stack will contain the elements in monotonic decreasing order.

Let’s illustrate the example for a monotonic decreasing stack using the array Arr[] = {7, 5, 9, 4}:

Below is the implementation of the above approach:

C++

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

// Function to implement monotonic decreasing stack
vector<int> monotonicDecreasing(vector<int>& nums) {
    int n = nums.size();
    stack<int> st;
    vector<int> result(n);

    // Traverse the array
    for (int i = 0; i < n; ++i) {
        // While stack is not empty AND top of stack is less than the current element
        while (!st.empty() && st.top() < nums[i]) {
            st.pop();
        }

        // Construct the result array
        if (!st.empty()) {
            result[i] = st.top();
        } else {
            result[i] = -1;
        }

        // Push the current element into the stack
        st.push(nums[i]);
    }

    return result;
}

int main() {
    vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6};
    vector<int> result = monotonicDecreasing(nums);

    cout << "Monotonic decreasing stack: ";
    for (int val : result) {
        cout << val << " ";
    }
    cout << endl;

    return 0;
}

Java

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class MonotonicDecreasing {
    public static List<Integer> monotonicDecreasing(int[] nums) {
        Stack<Integer> stack = new Stack<>();
        List<Integer> result = new ArrayList<>();

        // Traverse the array
        for (int num : nums) {
            // While stack is not empty AND top of stack is less than the current element
            while (!stack.isEmpty() && stack.peek() < num) {
                // Pop the top element from the stack
                stack.pop();
            }

            // Construct the result array
            if (!stack.isEmpty()) {
                result.add(stack.peek());
            } else {
                result.add(-1);
            }

            // Push the current element into the stack
            stack.push(num);
        }

        return result;
    }

    public static void main(String[] args) {
        int[] nums = {3, 1, 4, 1, 5, 9, 2, 6};
        List<Integer> result = monotonicDecreasing(nums);
        System.out.println("Monotonic decreasing stack: " + result);
    }
}

Python

def monotonicDecreasing(nums):
    stack = []
    result = []

    # Traverse the array
    for num in nums:
        # While stack is not empty AND top of stack is less than the current element
        while stack and stack[-1] < num:
            # Pop the top element from the stack
            stack.pop()
        
        # Construct the result array
        if stack:
            result.append(stack[-1])
        else:
            result.append(-1)
        
        # Push the current element into the stack
        stack.append(num)

    return result

# Example usage:
nums = [3, 1, 4, 1, 5, 9, 2, 6]
result = monotonicDecreasing(nums)
print("Monotonic decreasing stack:", result)

JavaScript

function monotonicDecreasing(nums) {
    let stack = [];
    let result = [];

    // Traverse the array
    for (let num of nums) {
        // While stack is not empty AND top of stack is less than the current element
        while (stack.length && stack[stack.length - 1] < num) {
            // Pop the top element from the stack
            stack.pop();
        }

        // Construct the result array
        if (stack.length) {
            result.push(stack[stack.length - 1]);
        } else {
            result.push(-1);
        }

        // Push the current element into the stack
        stack.push(num);
    }

    return result;
}

// Example usage:
let nums = [3, 1, 4, 1, 5, 9, 2, 6];
let result = monotonicDecreasing(nums);
console.log("Monotonic decreasing stack:", result);

Output

Monotonic decreasing stack: -1 3 -1 4 -1 -1 9 9

Complexity Analysis:

Time Complexity: O(N), each element is processed only twice, once for the push operation and once for the pop operation.
Auxiliary Space: O(N)

Introduction to Monotonic Stack – Data Structure and Algorithm Tutorials

A monotonic stack is a special data structure used in algorithmic problem-solving. Monotonic Stack maintaining elements in either increasing or decreasing order. It is commonly used to efficiently solve problems such as finding the next greater or smaller element in an array etc.

Monotonic Stack

Table of Content

What is Monotonic Stack?
Types of Monotonic Stack

Monotonic Increasing Stack
Monotonic Decreasing Stack

Applications of Monotonic Stack
Advantages of Monotonic Stack
Disadvantages of Monotonic Stack
Frequently Asked Questions (FAQs) on Monotonic Stack:

Monotonic Decreasing Stack

How to achieve Monotonic Decreasing Stack?

Introduction to Monotonic Stack – Data Structure and Algorithm Tutorials

Similar Reads