4.1 Monotonic Stack

চিনবেন কীভাবে

"next greater/smaller element", "how many days to wait", histogram/boundaries, stock span — for each element: "who is the first one bigger/smaller than me?"

Demo · approach · কোড — আগে নিজে চেষ্টা, আটকালে খুলুন

Demo: Largest Rectangle in Histogram — LC 84 (Hard — Google High)

Statement (Demo): Given an integer array heights where heights[i] is the height of bar i (each bar has width 1), return the area of the largest rectangle in the histogram. Example: heights=[2,1,5,6,2,3] → 10 | ⚡ n ≤ 10⁵, 0 ≤ heights[i] ≤ 10⁴

Approach: Keep indices on a stack with increasing heights. When a shorter bar arrives, pop — for the popped bar, the right boundary is the current index and the left boundary is the new stack top. Process a height-0 sentinel at the end to pop everything.

function largestRectangleArea(heights) {
  const stack = []; // indices, heights increasing
  let best = 0;
  for (let i = 0; i <= heights.length; i++) {
    const h = i === heights.length ? 0 : heights[i]; // sentinel at the end
    while (stack.length && heights[stack[stack.length - 1]] >= h) {
      const height = heights[stack.pop()];
      const left = stack.length ? stack[stack.length - 1] + 1 : 0;
      best = Math.max(best, height * (i - left));
    }
    stack.push(i);
  }
  return best;
}

Complexity: Time O(n) (each index pushed once, popped once), Space O(n)

প্রবলেম

Daily Temperaturesplan · দিন ০০৫ LC 739
(simplest form of the monotonic stack — do this first)
Statement: Given an integer array temperatures, return for each day how many days until a warmer temperature, or 0 if none comes.
Example: [73,74,75,71,69,72,76,73] → [1,1,4,2,1,1,0,0] | ⚡ n ≤ 10⁵, 30 ≤ temp ≤ 100
নোট · ফাঁকা
My solution — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেWhere I got stuck — কোন trap, ইংরেজিতে
Next Greater Element Iplan · দিন ০১৬ LC 496
Statement: Given two distinct integer arrays nums1 and nums2 (nums1 is a subset of nums2), for each element of nums1 return the first greater element to its right in nums2, or -1.
Example: nums1=[4,1,2], nums2=[1,3,4,2] → [-1,3,-1] | ⚡ n ≤ 1000
নোট · ফাঁকা
My solution — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেWhere I got stuck — কোন trap, ইংরেজিতে
Next Greater Element IILC 503
(circular → loop twice, index mod n)
Statement: Given a circular integer array nums, return the next greater number for every element (the search wraps around to the start), or -1.
Example: [1,2,1] → [2,-1,2] | ⚡ n ≤ 10⁴
নোট · ফাঁকা
My solution — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেWhere I got stuck — কোন trap, ইংরেজিতে
Online Stock SpanLC 901
Statement: Design StockSpanner whose next(price) returns today's span — how many consecutive days, ending today, had a price ≤ today's price.
Example: next calls [100,80,60,70,60,75,85] → [1,1,1,2,1,4,6] | ⚡ at most 10⁴ calls
নোট · ফাঁকা
My solution — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেWhere I got stuck — কোন trap, ইংরেজিতে

আরও দেখুন

Trapping Rain Water (stack solution) → primary entry in 1.1