# Monotonic Stack / Queue — डेटा स्ट्रक्चर और एल्गोरिदम

Source: https://www.geekswithgeeks.com/hi/dsa/monotonic-stack

> एक stack या deque जो बढ़ते या घटते क्रम में रखा जाता है, next-greater और sliding-window-min/max को O(n) में हल करने के लिए।

## क्रम में रखें

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

## अगला बड़ा element

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

```python
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 करें।

```python
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 जैसी समस्याओं के लिए।