Monotonic stack trzyma elementy w kolejności rosnącej albo malejącej. Używa się go do zadań typu „next greater/smaller element”, stock span czy histogram — często w O(n), bo każdy element jest wrzucany i zdejmowany co najwyżej raz.
function nextGreater(nums: number[]): number[] {
const res = Array(nums.length).fill(-1);
const st: number[] = []; // stack of indices
for (let i = 0; i < nums.length; i++) {
while (st.length && nums[st[st.length - 1]] < nums[i]) {
res[st.pop()!] = nums[i];
}
st.push(i);
}
return res;
}Rozwinięcie krótkiej odpowiedzi — co zwykle ma znaczenie w praktyce:
Poniżej dodatkowy przykład (bazuje na tym, co już jest w odpowiedzi):
function nextGreater(nums: number[]): number[] {
const res = Array(nums.length).fill(-1);
const st: number[] = []; // stack of indices
for (let i = 0; i < nums.length; i++) {
while (st.length && nums[st[st.length - 1]] < nums[i]) {
res[st.pop()!] = nums[i];
}
st.push(i);
}
return res;
}