Stacks

#include <stack>
 
stack<int> st;
 
// --- Modify ---
st.push(10);        // Push element onto top
st.push(20);
st.push(30);
st.emplace(40);     // Construct in-place (prefer over push for complex types)
st.pop();           // Remove top element (returns void — save top() first!)
 
// --- Access ---
cout << st.top();   // 30 — peek at top without removing (O(1))
cout << st.size();  // 3
cout << st.empty(); // false
 
// Warning: Always check empty() before calling top() or pop()!
while (!st.empty()) {
    cout << st.top() << " ";
    st.pop();
}
// Output: 30 20 10
 
// --- Underlying container options ---
stack<int>                  default_st;     // Uses deque (default)
stack<int, vector<int>>     vector_st;      // Uses vector (faster in practice)
stack<int, list<int>>       list_st;        // Uses list (rarely useful)

class StackArray {
    vector<int> data;
    int topIdx;
    int capacity;
 
public:
    StackArray(int cap) : topIdx(-1), capacity(cap), data(cap) {}
 
    void push(int val) {
        if (topIdx == capacity - 1) throw overflow_error("Stack overflow");
        data[++topIdx] = val;
    }
    void pop() {
        if (empty()) throw underflow_error("Stack underflow");
        topIdx--;
    }
    int top() const {
        if (empty()) throw underflow_error("Empty stack");
        return data[topIdx];
    }
    bool empty() const { return topIdx == -1; }
    int size()   const { return topIdx + 1; }
};
// All operations: O(1). No memory allocation after construction.

class StackDynamic {
    vector<int> data;
public:
    void push(int val)  { data.push_back(val); }
    void pop()          { if (!empty()) data.pop_back(); }
    int  top()    const { return data.back(); }
    bool empty()  const { return data.empty(); }
    int  size()   const { return data.size(); }
};
// All operations: O(1) amortized (vector doubling for push_back).

class StackList {
    struct Node { int val; Node* next; Node(int v, Node* n) : val(v), next(n) {} };
    Node* head = nullptr;
    int sz = 0;
public:
    void push(int val)  { head = new Node(val, head); sz++; }
    void pop()          { if (!head) return; Node* tmp = head; head = head->next; delete tmp; sz--; }
    int  top()    const { return head->val; }
    bool empty()  const { return head == nullptr; }
    int  size()   const { return sz; }
};
// All operations: O(1) guaranteed (no amortized). Slightly more memory (pointer overhead).

// Naive: O(n²) — for each element, scan right for next greater
for (int i = 0; i < n; i++)
    for (int j = i+1; j < n; j++)
        if (arr[j] > arr[i]) { nge[i] = arr[j]; break; }
 
// Monotonic stack: O(n)
stack<int> st;  // stores indices
for (int i = 0; i < n; i++) {
    while (!st.empty() && arr[st.top()] < arr[i]) {
        nge[st.top()] = arr[i];   // arr[i] is the NGE for the popped element
        st.pop();
    }
    st.push(i);
}
// Remaining elements in stack have no NGE → default value (e.g., -1)

// ─── Template: Find answer for each element when condition triggers ───────────
vector<int> result(n, DEFAULT_VALUE);
stack<int> st;  // Always store INDICES, not values (indices give more info)
 
for (int i = 0; i < n; i++) {
 
    // Pop phase: while stack is not empty AND monotonicity is violated
    while (!st.empty() && CONDITION(arr[st.top()], arr[i])) {
        int idx = st.top(); st.pop();
        result[idx] = ANSWER(arr[i], arr[idx]);   // Current element answers the popped one
    }
 
    // Push phase: current element enters the stack
    st.push(i);
}
// Note: any indices remaining in st when the loop ends have no answer found

vector<int> nextGreater(vector<int>& arr) {
    int n = arr.size();
    vector<int> nge(n, -1);   // Default: no NGE
    stack<int> st;             // Monotonically decreasing (indices)
 
    for (int i = 0; i < n; i++) {
        // Pop all elements smaller than current — their NGE is arr[i]
        while (!st.empty() && arr[st.top()] < arr[i]) {
            nge[st.top()] = arr[i];
            st.pop();
        }
        st.push(i);
    }
    return nge;
}
// Time: O(n), Space: O(n)
 
/*
  arr = [2, 1, 2, 4, 3]
  i=0: push 0.  st=[0]
  i=1: arr[1]=1 < arr[0]=2, no pop. push 1.  st=[0,1]
  i=2: arr[2]=2 > arr[1]=1 → nge[1]=2, pop. arr[0]=2 not < 2, stop. push 2. st=[0,2]
  i=3: arr[3]=4 > arr[2]=2 → nge[2]=4, pop. arr[0]=2 < 4 → nge[0]=4, pop. push 3. st=[3]
  i=4: arr[4]=3 < arr[3]=4, push. st=[3,4]
  Remaining in stack: nge[3]=nge[4]=-1
  Result: [4, 2, 4, -1, -1]
*/

vector<int> nextSmaller(vector<int>& arr) {
    int n = arr.size();
    vector<int> nse(n, -1);
    stack<int> st;   // Monotonically increasing
 
    for (int i = 0; i < n; i++) {
        // Pop all elements GREATER than current — their NSE is arr[i]
        while (!st.empty() && arr[st.top()] > arr[i]) {
            nse[st.top()] = arr[i];
            st.pop();
        }
        st.push(i);
    }
    return nse;
}
// Time: O(n), Space: O(n)

vector<int> prevGreater(vector<int>& arr) {
    int n = arr.size();
    vector<int> pge(n, -1);
    stack<int> st;   // Monotonically decreasing
 
    for (int i = 0; i < n; i++) {
        // Pop all elements SMALLER OR EQUAL to current
        while (!st.empty() && arr[st.top()] <= arr[i]) st.pop();
 
        // After popping, top of stack is PGE for current element
        if (!st.empty()) pge[i] = arr[st.top()];
 
        st.push(i);
    }
    return pge;
}

vector<int> prevSmaller(vector<int>& arr) {
    int n = arr.size();
    vector<int> pse(n, -1);
    stack<int> st;   // Monotonically increasing
 
    for (int i = 0; i < n; i++) {
        // Pop all elements GREATER OR EQUAL to current
        while (!st.empty() && arr[st.top()] >= arr[i]) st.pop();
 
        // Remaining top is PSE for current element
        if (!st.empty()) pse[i] = arr[st.top()];
 
        st.push(i);
    }
    return pse;
}

vector<int> nextGreaterCircular(vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n, -1);
    stack<int> st;
 
    for (int i = 0; i < 2 * n; i++) {
        int idx = i % n;
        while (!st.empty() && nums[st.top()] < nums[idx]) {
            result[st.top()] = nums[idx];
            st.pop();
        }
        if (i < n) st.push(idx);  // Only push indices in first pass
    }
    return result;
}
// Time: O(n), Space: O(n)

int largestRectangleArea(vector<int>& heights) {
    int n = heights.size();
 
    // Compute left boundary: index of Previous Smaller Element (or -1)
    vector<int> left(n), right(n);
    stack<int> st;
 
    for (int i = 0; i < n; i++) {
        while (!st.empty() && heights[st.top()] >= heights[i]) st.pop();
        left[i] = st.empty() ? -1 : st.top();
        st.push(i);
    }
 
    while (!st.empty()) st.pop();
 
    // Compute right boundary: index of Next Smaller Element (or n)
    for (int i = n-1; i >= 0; i--) {
        while (!st.empty() && heights[st.top()] >= heights[i]) st.pop();
        right[i] = st.empty() ? n : st.top();
        st.push(i);
    }
 
    // For each bar: area = height * width
    int maxArea = 0;
    for (int i = 0; i < n; i++) {
        int width = right[i] - left[i] - 1;
        maxArea = max(maxArea, heights[i] * width);
    }
    return maxArea;
}
// Time: O(n), Space: O(n)
 
/*
  heights = [2, 1, 5, 6, 2, 3]
  left  (PSE index): [-1, -1, 1, 2,  1,  4]
  right (NSE index): [ 1,  6, 4, 4,  6,  6]
  widths:            [  1,  5, 2, 1,  4,  1]
  areas:             [  2,  5,10, 6,  8,  3]
  maxArea = 10
*/
 
// One-pass solution using a single monotonic stack
int largestRectangleArea_onePass(vector<int>& heights) {
    int n = heights.size();
    stack<int> st;
    int maxArea = 0;
 
    for (int i = 0; i <= n; i++) {
        int h = (i == n) ? 0 : heights[i];  // Sentinel 0 flushes the stack
        while (!st.empty() && heights[st.top()] > h) {
            int height = heights[st.top()]; st.pop();
            int width  = st.empty() ? i : i - st.top() - 1;
            maxArea = max(maxArea, height * width);
        }
        st.push(i);
    }
    return maxArea;
}
// Time: O(n), Space: O(n)

bool isValid(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if (st.empty()) return false;
            char top = st.top(); st.pop();
            if (c == ')' && top != '(') return false;
            if (c == ']' && top != '[') return false;
            if (c == '}' && top != '{') return false;
        }
    }
    return st.empty();  // All openers were matched
}
// Time: O(n), Space: O(n)

int evalRPN(vector<string>& tokens) {
    stack<long long> st;
 
    for (const string& tok : tokens) {
        if (tok == "+" || tok == "-" || tok == "*" || tok == "/") {
            long long b = st.top(); st.pop();  // Right operand (popped second)
            long long a = st.top(); st.pop();  // Left operand (popped first)
            if      (tok == "+") st.push(a + b);
            else if (tok == "-") st.push(a - b);
            else if (tok == "*") st.push(a * b);
            else                 st.push(a / b);  // Truncates toward zero in C++
        } else {
            st.push(stoll(tok));   // Operand: push as number
        }
    }
    return st.top();
}
// Time: O(n), Space: O(n)

int calculate(string s) {
    stack<int> st;
    int num = 0;
    char op = '+';   // Treat the first number as preceded by '+'
 
    for (int i = 0; i < (int)s.size(); i++) {
        char c = s[i];
 
        if (isdigit(c)) {
            num = num * 10 + (c - '0');   // Build multi-digit number
        }
 
        // Process when we hit an operator OR reach end of string
        if ((!isdigit(c) && c != ' ') || i == (int)s.size() - 1) {
            if      (op == '+') st.push(num);
            else if (op == '-') st.push(-num);
            else if (op == '*') { int top = st.top(); st.pop(); st.push(top * num); }
            else if (op == '/') { int top = st.top(); st.pop(); st.push(top / num); }
            op = c;    // Update operator for next number
            num = 0;   // Reset number
        }
    }
 
    int result = 0;
    while (!st.empty()) { result += st.top(); st.pop(); }
    return result;
}
// Time: O(n), Space: O(n)
 
/*
  s = "3+2*2"
  Process 3 with op='+': push 3.  st=[3]
  Process 2 with op='*': push 3,2 but * so pop 3... wait let's trace op changes:
 
  i=0: c='3', num=3
  i=1: c='+', op was '+', push(3), op='+', num=0. stack=[3]
  i=2: c='2', num=2
  i=3: c='*', op='+', push(2),    op='*', num=0. stack=[3,2]  <- wrong!
 
  Actually re-trace with correct op tracking:
  Initially op='+', num=0.
  c='3': num=3
  c='+': op was '+', push(3). op='+'. num=0. st=[3]
  c='2': num=2
  c='*': op was '+', push(2). op='*'. num=0. st=[3,2]
  c='2': num=2  (end of string too)
  i=last: op='*', pop 2, push 2*2=4. st=[3,4]
  sum = 7. ✅
*/

string decodeString(string s) {
    stack<int>    countSt;    // Stack of repeat counts
    stack<string> strSt;      // Stack of partial strings
    string curr = "";
    int num = 0;
 
    for (char c : s) {
        if (isdigit(c)) {
            num = num * 10 + (c - '0');   // Handle multi-digit counts
        } else if (c == '[') {
            countSt.push(num);    // Save current count
            strSt.push(curr);     // Save current string
            num  = 0;             // Reset for next number
            curr = "";            // Reset for inner content
        } else if (c == ']') {
            int k    = countSt.top(); countSt.pop();
            string inner = curr;
            curr = strSt.top();   strSt.pop();   // Restore outer string
            for (int i = 0; i < k; i++) curr += inner;  // Repeat inner k times
        } else {
            curr += c;
        }
    }
    return curr;
}
// Time: O(n * max_k) where max_k is maximum repeat count
// Space: O(n)
 
/*
  s = "3[a2[c]]"
  c='3': num=3
  c='[': push count=3, push curr="", reset. countSt=[3], strSt=[""]
  c='a': curr="a"
  c='2': num=2
  c='[': push count=2, push curr="a", reset. countSt=[3,2], strSt=["","a"]
  c='c': curr="c"
  c=']': k=2, inner="c", curr="a"+"cc"="acc". countSt=[3], strSt=[""]
  c=']': k=3, inner="acc", curr=""+"accaccacc"="accaccacc". Done.
  Result: "accaccacc" ✅
*/

int longestValidParentheses(string s) {
    stack<int> st;
    st.push(-1);    // Sentinel: base for length calculation
 
    int maxLen = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] == '(') {
            st.push(i);   // Push index of '('
        } else {
            st.pop();     // Match with top (or remove the sentinel)
            if (st.empty()) {
                st.push(i);   // New base: unmatched ')' at i
            } else {
                maxLen = max(maxLen, i - st.top());
            }
        }
    }
    return maxLen;
}
// Time: O(n), Space: O(n)
 
/*
  s = "()(()"
  stack initially: [-1]
  i=0 '(': push 0.  st=[-1,0]
  i=1 ')': pop 0.   st=[-1]. len = 1-(-1) = 2
  i=2 '(': push 2.  st=[-1,2]
  i=3 '(': push 3.  st=[-1,2,3]
  i=4 ')': pop 3.   st=[-1,2]. len = 4-2 = 2
  maxLen = 2
*/

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> st;
    TreeNode* curr = root;
 
    while (curr || !st.empty()) {
        // Go as far left as possible
        while (curr) {
            st.push(curr);
            curr = curr->left;
        }
        // Process: pop, visit, go right
        curr = st.top(); st.pop();
        result.push_back(curr->val);
        curr = curr->right;
    }
    return result;
}
// Time: O(n), Space: O(h) where h = height

vector<int> preorderTraversal(TreeNode* root) {
    if (!root) return {};
    vector<int> result;
    stack<TreeNode*> st;
    st.push(root);
 
    while (!st.empty()) {
        TreeNode* node = st.top(); st.pop();
        result.push_back(node->val);   // Visit root first
        if (node->right) st.push(node->right);  // Push right before left
        if (node->left)  st.push(node->left);   // Left is processed first (LIFO)
    }
    return result;
}
// Time: O(n), Space: O(h)

// Method: Reverse of (Root → Right → Left) preorder
// Compute Root→Right→Left using a stack, then reverse the result.
vector<int> postorderTraversal(TreeNode* root) {
    if (!root) return {};
    vector<int> result;
    stack<TreeNode*> st;
    st.push(root);
 
    while (!st.empty()) {
        TreeNode* node = st.top(); st.pop();
        result.push_back(node->val);
        if (node->left)  st.push(node->left);   // Push left first (processed second)
        if (node->right) st.push(node->right);  // Push right second (processed first)
    }
    reverse(result.begin(), result.end());  // Reverse: Root→Right→Left → Left→Right→Root
    return result;
}
// Time: O(n), Space: O(h)

void dfsIterative(int start, int n, vector<vector<int>>& adj) {
    vector<bool> visited(n, false);
    stack<int> st;
 
    st.push(start);
    while (!st.empty()) {
        int node = st.top(); st.pop();
        if (visited[node]) continue;   // Skip if already visited
        visited[node] = true;
        cout << node << " ";
 
        // Push neighbors (note: order differs from recursive DFS)
        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) st.push(neighbor);
        }
    }
}
// Time: O(V + E), Space: O(V)
// Note: iterative DFS may visit nodes in different order than recursive DFS
//       due to the difference between stack push order and recursion order.

bool isValid(string s) {
    stack<char> st;
    for (char c : s) {
        if (c=='(' || c=='[' || c=='{') { st.push(c); continue; }
        if (st.empty()) return false;
        char top = st.top(); st.pop();
        if (c==')' && top!='(') return false;
        if (c==']' && top!='[') return false;
        if (c=='}' && top!='{') return false;
    }
    return st.empty();
}
// Time: O(n), Space: O(n)

class MinStack {
    stack<int> st;
    stack<int> minSt;   // Parallel stack: minSt.top() = current minimum
 
public:
    void push(int val) {
        st.push(val);
        // Push to minSt: smaller of new val and current min
        minSt.push(minSt.empty() ? val : min(val, minSt.top()));
    }
    void pop() {
        st.pop();
        minSt.pop();
    }
    int top()    { return st.top(); }
    int getMin() { return minSt.top(); }   // Always O(1)
};
 
/*
  push(5):  st=[5],    minSt=[5]
  push(3):  st=[5,3],  minSt=[5,3]
  push(7):  st=[5,3,7],minSt=[5,3,3]   <- min is still 3
  getMin()  = 3
  pop():    st=[5,3],  minSt=[5,3]
  getMin()  = 3
  pop():    st=[5],    minSt=[5]
  getMin()  = 5
*/
// All operations: O(1). Space: O(n) for both stacks.

vector<int> dailyTemperatures(vector<int>& T) {
    int n = T.size();
    vector<int> answer(n, 0);
    stack<int> st;   // Monotonically decreasing stack of indices
 
    for (int i = 0; i < n; i++) {
        while (!st.empty() && T[st.top()] < T[i]) {
            answer[st.top()] = i - st.top();   // Days to wait = i - popped index
            st.pop();
        }
        st.push(i);
    }
    return answer;   // Unprocessed indices keep their default 0
}
// Time: O(n), Space: O(n)
 
/*
  T = [73,74,75,71,69,72,76,73]
  i=0: push 0. st=[0]
  i=1: T[1]=74>T[0]=73 → ans[0]=1-0=1, pop. push 1. st=[1]
  i=2: T[2]=75>T[1]=74 → ans[1]=2-1=1, pop. push 2. st=[2]
  i=3: T[3]=71<T[2]=75, push 3. st=[2,3]
  i=4: T[4]=69<T[3]=71, push 4. st=[2,3,4]
  i=5: T[5]=72>T[4]=69 → ans[4]=5-4=1, pop.
       T[5]=72>T[3]=71 → ans[3]=5-3=2, pop. push 5. st=[2,5]
  i=6: T[6]=76>T[5]=72 → ans[5]=6-5=1, pop.
       T[6]=76>T[2]=75 → ans[2]=6-2=4, pop. push 6. st=[6]
  i=7: T[7]=73<T[6]=76, push 7. st=[6,7]
  Remaining: ans[6]=0, ans[7]=0
  Result: [1,1,4,2,1,1,0,0]
*/

vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
    // Build NGE map for nums2 using monotonic stack
    unordered_map<int,int> nge;
    stack<int> st;   // Decreasing stack of values
 
    for (int x : nums2) {
        while (!st.empty() && st.top() < x) {
            nge[st.top()] = x;
            st.pop();
        }
        st.push(x);
    }
    // Remaining in stack have no NGE — map will return 0 (use count check)
 
    vector<int> result;
    for (int x : nums1) {
        result.push_back(nge.count(x) ? nge[x] : -1);
    }
    return result;
}
// Time: O(n + m), Space: O(n)

string removeKdigits(string num, int k) {
    string result;   // Acts as our stack (string for easy substring)
 
    for (char c : num) {
        // While we can still remove (k > 0) and top is larger, remove it
        while (k > 0 && !result.empty() && result.back() > c) {
            result.pop_back();
            k--;
        }
        result.push_back(c);
    }
 
    // If k > 0 remaining, remove from the right (largest digits are there now)
    while (k-- > 0) result.pop_back();
 
    // Remove leading zeros
    int start = result.find_first_not_of('0');
    result = (start == string::npos) ? "0" : result.substr(start);
 
    return result;
}
// Time: O(n), Space: O(n)
 
/*
  num = "1432219", k = 3
  c='1': result="1"
  c='4': 4>1, push.  result="14"
  c='3': 3<4, pop(4) k=2, 3>1, push. result="13"
  c='2': 2<3, pop(3) k=1, 2>1, push. result="12"
  c='2': 2>=2, push. result="122"
  c='1': 1<2, pop(2) k=0. push. result="121" (k=0, stop popping)
  c='9': k=0, just push. result="1219"
  Trim leading zeros: "1219"
  Result: "1219"
*/

int evalRPN(vector<string>& tokens) {
    stack<long long> st;
    for (const string& t : tokens) {
        if (t=="+"||t=="-"||t=="*"||t=="/") {
            long long b=st.top(); st.pop();
            long long a=st.top(); st.pop();
            if (t=="+") st.push(a+b);
            else if (t=="-") st.push(a-b);
            else if (t=="*") st.push(a*b);
            else             st.push(a/b);
        } else {
            st.push(stoll(t));
        }
    }
    return (int)st.top();
}
// Time: O(n), Space: O(n)

string decodeString(string s) {
    stack<int>    countSt;
    stack<string> strSt;
    string curr = "";
    int num = 0;
 
    for (char c : s) {
        if (isdigit(c))  { num = num*10 + (c-'0'); }
        else if (c=='[') { countSt.push(num); strSt.push(curr); num=0; curr=""; }
        else if (c==']') {
            int k = countSt.top(); countSt.pop();
            string inner = curr;
            curr = strSt.top(); strSt.pop();
            for (int i=0; i<k; i++) curr += inner;
        } else { curr += c; }
    }
    return curr;
}
// Time: O(n * max_k), Space: O(n)

vector<int> asteroidCollision(vector<int>& asteroids) {
    stack<int> st;
 
    for (int a : asteroids) {
        bool destroyed = false;
 
        // Collision: a moves left (a<0) and top moves right (st.top()>0)
        while (!st.empty() && a < 0 && st.top() > 0) {
            if (st.top() < -a) {
                st.pop();        // Stack top destroyed, continue checking
                continue;
            } else if (st.top() == -a) {
                st.pop();        // Both destroyed
            }
            destroyed = true;    // Current asteroid destroyed
            break;
        }
        if (!destroyed) st.push(a);
    }
 
    vector<int> result;
    while (!st.empty()) { result.push_back(st.top()); st.pop(); }
    reverse(result.begin(), result.end());
    return result;
}
// Time: O(n), Space: O(n)
 
/*
  asteroids = [5, 10, -5]
  a=5:   st=[5]   (moving right, no collision)
  a=10:  st=[5,10] (moving right)
  a=-5:  -5 collides with 10. |10| > |-5|, -5 destroyed. st=[5,10]
  Result: [5, 10]
*/

int carFleet(int target, vector<int>& position, vector<int>& speed) {
    int n = position.size();
    vector<pair<int,double>> cars(n);
 
    for (int i = 0; i < n; i++)
        cars[i] = {position[i], (double)(target - position[i]) / speed[i]};
 
    sort(cars.rbegin(), cars.rend());  // Sort by position descending (closest to target first)
 
    stack<double> st;   // Stack of arrival times
    for (auto& [pos, time] : cars) {
        // If this car arrives LATER than the current fleet leader, it's a new fleet
        if (st.empty() || time > st.top()) {
            st.push(time);
        }
        // Otherwise, it catches up and merges (don't push — it joins the fleet ahead)
    }
    return st.size();
}
// Time: O(n log n), Space: O(n)

int largestRectangleArea(vector<int>& heights) {
    int n = heights.size();
    stack<int> st;
    int maxArea = 0;
 
    for (int i = 0; i <= n; i++) {
        int h = (i == n) ? 0 : heights[i];   // Sentinel 0 flushes remaining
        while (!st.empty() && heights[st.top()] > h) {
            int height = heights[st.top()]; st.pop();
            int width  = st.empty() ? i : i - st.top() - 1;
            maxArea = max(maxArea, height * width);
        }
        st.push(i);
    }
    return maxArea;
}
// Time: O(n), Space: O(n)

int longestValidParentheses(string s) {
    stack<int> st;
    st.push(-1);
    int maxLen = 0;
 
    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] == '(') {
            st.push(i);
        } else {
            st.pop();
            if (st.empty()) st.push(i);   // Unmatched ')' becomes new base
            else maxLen = max(maxLen, i - st.top());
        }
    }
    return maxLen;
}
// Time: O(n), Space: O(n)

int maxWidthRamp(vector<int>& nums) {
    int n = nums.size();
    stack<int> st;
 
    // Build decreasing stack: potential left endpoints
    for (int i = 0; i < n; i++) {
        if (st.empty() || nums[i] < nums[st.top()]) {
            st.push(i);
        }
    }
 
    int maxWidth = 0;
    // Scan from right: greedily match with furthest left endpoint
    for (int j = n - 1; j >= 0; j--) {
        while (!st.empty() && nums[st.top()] <= nums[j]) {
            maxWidth = max(maxWidth, j - st.top());
            st.pop();
        }
    }
    return maxWidth;
}
// Time: O(n), Space: O(n)