Baseline Stack and Queues · Monotonic Stack and Queue O(n) · O(n)
A battery pack logs cell voltages in a row, and the diagnostics tool must report, for each cell, the nearest cell to its left that read strictly lower — the baseline that cell is measured against. Cells with no weaker predecessor get a sentinel of -1.
Input: An integer array arr of cell readings.
Output: Return an array where entry i is the nearest strictly smaller value to the left of arr[i], or -1 if none exists.
1 <= arr.length <= 10^5-10^9 <= arr[i] <= 10^9Input: {"arr":[1,6,2]}
Output: [-1,1,1]
Nothing sits left of 1; both 6 and 2 look back to the 1 as their nearest smaller value.
Input: {"arr":[5,4,3,2,1]}
Output: [-1,-1,-1,-1,-1]
A strictly decreasing row never finds a smaller value to its left.