4.1 Monotonic Stack

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

"next greater/smaller element", "কতদিন অপেক্ষা", histogram/boundary, stock span — প্রতিটা এলিমেন্টের জন্য "আমার চেয়ে বড়/ছোট প্রথম কে" প্রশ্ন

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

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

Statement (Demo): integer array heights দেওয়া যেখানে heights[i] = i-তম bar-এর উচ্চতা, প্রতিটা bar-এর width 1। histogram-এ সবচেয়ে বড় rectangle-এর area বের করুন। উদাহরণ: heights=[2,1,5,6,2,3] → 10 | ⚡ n ≤ 10⁵, 0 ≤ heights[i] ≤ 10⁴

Approach: stack-এ index রাখুন যাতে height increasing থাকে। ছোট height এলে pop করুন — pop হওয়া bar-এর জন্য ডান boundary = এখনকার index, বাম boundary = stack-এর নতুন top। শেষে সব pop করাতে sentinel হিসেবে height 0 প্রসেস করুন।

function largestRectangleArea(heights) {
  const stack = []; // index জমা, height increasing
  let best = 0;
  for (let i = 0; i <= heights.length; i++) {
    const h = i === heights.length ? 0 : heights[i]; // শেষে sentinel
    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) (প্রতিটা index একবার push, একবার pop), Space O(n)

প্রবলেম

Daily Temperaturesplan · দিন ০৩০ LC 739
(monotonic stack-এর সহজতম রূপ — আগে এটা)
Statement: integer array temperatures দেওয়া — প্রতিদিনের জন্য বলুন কত দিন অপেক্ষা করলে warmer temperature পাওয়া যাবে। না পাওয়া গেলে 0।
উদাহরণ: [73,74,75,71,69,72,76,73] → [1,1,4,2,1,1,0,0] | ⚡ n ≤ 10⁵, 30 ≤ temp ≤ 100
নোট · ফাঁকা
আমার সমাধান — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেযে সমস্যা হয়েছিল — কোন trap বা edge case-এ আটকালেন
Next Greater Element Iplan · দিন ০৩৬ LC 496
Statement: দুটো distinct integer array nums1 ও nums2 দেওয়া (nums1 হলো nums2-এর subset)। nums1-এর প্রতিটা element-এর জন্য nums2-এ তার পরের first greater element বের করুন। না থাকলে -1।
উদাহরণ: nums1=[4,1,2], nums2=[1,3,4,2] → [-1,3,-1] | ⚡ n ≤ 1000
নোট · ফাঁকা
আমার সমাধান — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেযে সমস্যা হয়েছিল — কোন trap বা edge case-এ আটকালেন
Next Greater Element IILC 503
(circular → দুইবার লুপ, index mod n)
Statement: circular integer array nums দেওয়া — প্রতিটা element-এর জন্য next greater number বের করুন (circular মানে শেষের পর আবার শুরু থেকে খোঁজে)। না থাকলে -1।
উদাহরণ: [1,2,1] → [2,-1,2] | ⚡ n ≤ 10⁴
নোট · ফাঁকা
আমার সমাধান — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেযে সমস্যা হয়েছিল — কোন trap বা edge case-এ আটকালেন
Online Stock SpanLC 901
Statement: একটা StockSpanner class design করুন — next(price) method call করলে আজকের price ও তার আগের কতদিন price ≤ আজকের price ছিল তার span return করবে।
উদাহরণ: next calls: [100,80,60,70,60,75,85] → [1,1,1,2,1,4,6] | ⚡ max 10⁴ calls
নোট · ফাঁকা
আমার সমাধান — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেযে সমস্যা হয়েছিল — কোন trap বা edge case-এ আটকালেন

আরও দেখুন

Trapping Rain Water (stack solution) → primary এন্ট্রি 1.1-এ