Circular Array
อาร์เรย์ที่ตัวสุดท้ายเชื่อมกับตัวแรก (วนรอบ)
ปัญหา
รับ Circular Array หา Next Greater Element ของแต่ละตัว (หาไปทางขวา วนรอบได้) หากไม่มีให้ -1
ตัวอย่าง
const arr = [7, 8, 7];
7 → 8, 8 → -1, 7 → 8 → ผลลัพธ์ [8, -1, 8]
โค้ดตัวอย่าง (Monotonic Stack)
const arr = [7, 8, 7];
const nextGreaterElement = (arr = []) => {
const res = []; const stack = [];
if (!arr || arr.length < 1) return res;
for (let i = 0; i < arr.length; i++) {
while (stack.length > 0 && arr[stack[stack.length - 1]] < arr[i]) {
const small = stack.pop(); res[small] = arr[i];
}
stack.push(i);
}
for (let i = 0; i < arr.length; i++) {
while (stack.length > 0 && arr[stack[stack.length - 1]] < arr[i]) {
const small = stack.pop(); res[small] = arr[i];
}
}
const rem = stack.length;
for (let i = 0; i < rem; i++) { res[stack.pop()] = -1; }
return res;
};
console.log(nextGreaterElement(arr));
คำอธิบาย
ใช้ Stack เก็บดัชนีที่ยังไม่เจอค่ามากกว่า วน 2 รอบเพื่อครอบคลุม Circular
ผลลัพธ์
[8, -1, 8]
