Mảng vòng (Circular Array)
Mảng mà phần tử tiếp theo của phần tử cuối là phần tử đầu. Đây là khái niệm logic, bộ nhớ vẫn liên tục.
Vấn đề
Cần viết hàm JS nhận mảng vòng arr. Trả về mảng chứa phần tử lớn hơn tiếp theo (next greater element) cho mỗi phần tử. Tìm vòng tròn sang phải. Nếu không có, dùng -1.
Ví dụ:
const arr = [7, 8, 7];
Kết quả:
const output = [8, -1, 8];
Giải thích:
Cả hai 7 đều có next greater là 8. Với 8 không có phần tử lớn hơn -> -1.
Ví dụ
Mã thực hiện:
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));
Giải thích code:
Duyệt mảng, nếu thấy phần tử lớn hơn phần tử trong stack, gán res[small] = phần tử lớn hiện tại. Lặp lại từ đầu để xử lý phần tử chưa tìm thấy next greater. Cuối cùng gán -1 cho phần tử còn lại trong stack.
Kết quả
Kết quả in ra console:
[8, -1, 8]