Monotonic Stack

Monotonic : A sequence or function that is either entirely non-increasing or entirely non-decreasing.
Stack : A data structure using LIFO (Last In First Out ) strategy.

Is Monotonic Stack a Data Structure ?
No . Its a technique or approach that uses stack data structure , or some other data structure that can simulate stack LIFO behaviour.

What is a Monotonic Stack?
A Monotonic stack is a variation of the traditional stack data structure that maintains either a strictly increasing or strictly decreasing order of elements. Unlike a regular stack, where elements can be inserted and removed freely, a monotonic stack enforces a specific order to its elements.

When to use Monotonic Stack Technique ?
In problems where we need to process

• Next greater Element
• Next smaller Element
• Previous greater Element
• Previous smaller Element
• Lexicographically Smallest/Greatest
• Histogram Related Problems left and right boundaries for each bar

Basic Template :

void monotonicStack(const vector<int>& arr) {
    stack<int> st;
    for (int i = 0; i < arr.size(); ++i) {
			while(STACK NOT EMPTY  &&   st.top() OPERATOR arr[i] && other Logic given in problem ){
					//Extract the stack top
					//POP  the element 
					
					//Use the current element and STACK TOP to update result
					
					}
			
			//Push in stack
    }
	
	//at this point we have a monotonic stack in our hand
}

Types of monotonic stack (Bottom to top)

• Strictly increasing stack
• Non-decreasing stack
• Strictly decreasing stack
• Non-increasing stack

Problem 1 : ✏️✏️✏️ 739. Daily Temperatures (Next Greater)

Problem Statement :
Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Approach:

Problem wants us to find the Next Greater Element Index(NGEI) .

Difference of the NGEI and the current index tells the number of days to wait for a warmer day .

For each temperature, we check if it is greater than the temperature of the day represented by the index stored at the top of the stack.
If it is greater, it means we have found a warmer temperature for the day represented by that index. We keep popping elements from the stack until we find a temperature higher than the current temperature or until the stack becomes empty. For each popped element, we update the corresponding answer in the answer array.

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& nums) {
        int n = nums.size();
        stack<int> st;
        vector<int>res(n,0);
        // find next greeater
        for (int i = 0; i < n; i++) {
            int ele = nums[i];
            while (!st.empty() && ele > nums[st.top()]) {
                res[st.top()] = i - st.top();
                st.pop();
            }
            st.push(i); 
        }
        return res;
    }
};

Problem 2 : ✏️✏️✏️402. Remove K Digits(Constrained Monotonic Stack )

Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.

Example: For "1234591234" we delete 9 to make it minimal => 123451234

Key observations:

If the number is increasing in nature at each digit then it is the lowest number .
For each character, it aims to find the next smaller element (digit) to its right.

Constrained monotonic stack: maintains a stack with the constraint of removing a specific number of elements (k) while ensuring a monotonic property.
Explained Solution in Detail

The algorithm compares each character ch with the last character in the ans string(acting as monotonic increasing stack). If ch is smaller than the last character in ans, it means ch is the next smaller element compared to the last element in ans. The algorithm removes elements from string ans until ch becomes the next smaller element

class Solution {
public:
    string removeKdigits(string num, int k) {
        string ans="";// this will represent the stack 
        for(auto ch: num){
            while(ans.size() && ch < ans.back() && k){
                ans.pop_back();
                k--;
            }
            if(ans.size()==0 && ch=='0')continue;
            ans.push_back(ch);
        }

        while(ans.size() && k--)ans.pop_back();

        if(ans.size()>0)return ans;
        return "0";//
    }
};

Problem 3 : ✏️✏️✏️ Remove Duplicate Letters

Problem : Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical orderamong all possible results.

Smallest lexicographical order is the hint for using Monotonic Stack.

Monotonic increasing stack is built to ensure that the resulting string is the smallest in lexicographical order among all possible results. The stack is maintained in such a way that it only contains characters in increasing order, ensuring that when a character is added to the stack, it maintains the lexicographical order. Additionally, it also pops elements from the stack when necessary to ensure that the final string is the smallest possible.

Our primary goal is to form a monotonic increasing stack

class Solution {
public:
    string removeDuplicateLetters(string s) {
        stack<int>st;
        vector<bool>vis(26,false);// CAN ALSO USE AN UNORDERED MAP <char,bool>
        //it is marked true if character is in stack , false otherwise
        vector<int>freq(26,0);// FREQUENCY TELLS IF MORE OCCURENCE COME IN FUTURE
        
        for(auto it: s)
            freq[it-'a']++;

        for(int i=0;i<s.length();i++){
            char ch=s[i];
            freq[ch-'a']--;
            if(vis[ch-'a']==false){
                while(!st.empty() && st.top() > ch && freq[st.top()-'a']>0){
                    vis[st.top()-'a']=false;
                    st.pop();
                }
            vis[ch-'a']=true;
            st.push(ch);
            }
        }
        string res="";
        while (!st.empty()) {
            res.push_back(st.top());
            st.pop();
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

Problems List

1. Single Pass

Input Type : Array / Strings

• 496. Next Greater Element I
• 503. Next Greater Element II (Medium)
• 402. Remove K Digits (Medium)Next Smaller
• 739. Daily Temperatures (Medium) Next Greater
• 901. Online Stock Span (Medium) Previous Greater
• 1081. Smallest Subsequence of Distinct Characters (Medium)
• 456. 132 Pattern (Medium)
• 316. Remove Duplicate Letters (Medium)
• 1673. Find the Most Competitive Subsequence
• 42. Trapping Rain Water (Hard)

2. Two or more Pass

Input Type : Array / Matrix

• 907. Sum of Subarray Minimums (Optimal 1-Pass exists )
• 84. Largest Rectangle in Histogram (Optimal 1-Pass exists )
• 85. Maximal Rectangle Uses Concepts of previous problem 84

3. Monotonic Stack on Linked List

Input Type : Linked List

• 1019. Next Greater Node In Linked List
• 2487. Remove (Next Greater) Nodes From Linked List
• 2289. Steps to Make Array Non-decreasing

Summary :