Monotonic Stack / Queue

क्रम में रखें

Monotonic stack केवल वे elements push करता है जो stack को बढ़ता (या घटता) रखें। Push करने से पहले, जो क्रम तोड़ता है उसे pop करें। हर element अधिकतम एक बार push और एक बार pop होता है, जिससे कुल O(n) मिलता है, भले पहली नज़र में समस्या O(n^2) लगे।

अगला बड़ा element

दाएँ से बाएँ स्कैन करें (या indices के साथ बाएँ से दाएँ)। Push करने से पहले छोटे elements pop करें — जो top पर बचे वही next greater है।

def next_greater(nums):
    res = [-1] * len(nums)
    stack = []  # indices, values decreasing bottom to top
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            res[stack.pop()] = x
        stack.append(i)
    return res

Output:

next_greater([2, 1, 2, 4, 3])
# [4, 2, 4, -1, -1]

Sliding window maximum

Indices का एक monotonic deque, window का max आगे रखता है। जो indices window से बाहर हो जाएँ उन्हें हटाएँ, और append करने से पहले पीछे के छोटे values pop करें।

from collections import deque

def max_sliding_window(nums, k):
    dq, res = deque(), []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            res.append(nums[dq[0]])
    return res

पैटर्न पहचानें

Monotonic stack/queue इस्तेमाल करें: next greater/smaller element, histogram में सबसे बड़ा rectangle, sliding window max/min, और stock-span जैसी समस्याओं के लिए।