Monotonic Stack Patterns
Five prompts on monotonic stacks for next-greater-element, daily temperatures, and largest rectangle. Mostly implementation with one trace and one bug hunt.
812 views
23
Implement nextGreaterElement(nums) returning an array where out[i] is the next strictly greater value to the right of nums[i], or -1 if none. Aim for O(n).
Examples
Example 1:
Input: nums = [2, 1, 2, 4, 3]
Output: [4, 2, 4, -1, -1]
Explanation: Walk left to right with a stack of indices. For each new value, pop indices whose values are strictly smaller; they have just found their next-greater (current value). Push the current index. The remaining stack at the end gets -1.function nextGreaterElement(nums) {
// TODO: monotonic decreasing stack of indices
}Implement dailyTemperatures(temps) returning an array out where out[i] is the number of days until a strictly warmer temperature, or 0 if none.
Examples
Example 1:
Input: temps = [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]
Explanation: Same monotonic-stack-of-indices pattern as next-greater. For each new day, pop indices with strictly smaller temperatures and write out[j] = i - j. Days that never see a warmer follow-up stay at 0.function dailyTemperatures(temps) {
// TODO: stack of indices, fill out[i] when warmer day arrives
}Trace it. Run nextGreaterElement([2, 1, 3]) step by step. List the stack contents and out after each iteration.
Examples
Example 1:
Input: nums = [2, 1, 3]
Output: [3, 3, -1]
Explanation: i = 0: push 0, stack [0]. i = 1: nums[0] = 2 >= 1, no pops, push 1, stack [0, 1]. i = 2: nums[1] = 1 < 3, pop 1, out[1] = 3. nums[0] = 2 < 3, pop 0, out[0] = 3. Push 2, stack [2]. Final out = [3, 3, -1].function nextGreaterElement(nums) {
const out = new Array(nums.length).fill(-1);
const stack = [];
for (let i = 0; i < nums.length; i++) {
while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
out[stack.pop()] = nums[i];
}
stack.push(i);
}
return out;
}When does a monotonic stack maintain a non-decreasing vs a non-increasing stack? Give one canonical problem for each.
Spot the bug. This prevGreaterOrEqual(nums) is meant to return, for each index, the previous greater-or-equal value (or -1 if none). It returns the wrong answer on inputs that contain repeated values.
Examples
Example 1:
Input: nums = [3, 3]
Output (buggy version): [-1, -1]
Output (fixed version): [-1, 3]
Explanation: The buggy pop condition stack.top <= nums[i] also pops equal values, but an equal predecessor is a valid 'greater-or-equal' answer. The fix pops only when stack.top < nums[i].function prevGreaterOrEqual(nums) {
const out = new Array(nums.length).fill(-1);
const stack = [];
for (let i = 0; i < nums.length; i++) {
while (stack.length && stack[stack.length - 1] <= nums[i]) {
stack.pop();
}
if (stack.length) out[i] = stack[stack.length - 1];
stack.push(nums[i]);
}
return out;
}