β¨ Algorithm
To find the "next" element based on some criteria
- When stack is not empty, before we push a num onto the stack, we first pop from the stack if the monotonic property would be violated.
- Store value (or index) to the stack.
β¬οΈπ₯ (A) Find larger value
// nums[]
const stack = [];
for (const [i, num] of nums.entries()) {
// When current value is greater than last value in stack
// nums[i] > nums[stack.at(-1)];
// the larger value is found.
while (stack.length && nums[stack.at(-1)] < num) {
const pop = stack.pop();
// do something
}
stack.push(i);
}
{/* ### β¬οΈπ‘ (A.1) Tips */}
β¬οΈπ₯ (B) Find smaller value
// nums[]
const stack = [];
for (const [i, num] of nums.entries()) {
// When current value is smaller than last value in stack
// nums[i] < nums[stack.at(-1)];
// the smaller value is found.
while (stack.length && nums[stack.at(-1)] > num) {
const pop = stack.pop();
// do something
}
stack.push(i);
}
{/* ### β¬οΈπ‘ (A.1) Tips */}