Phần tử lớn hơn tiếp theo trong mảng tròn trong JavaScript

Mảng tròn

Mảng trong đó phần tử tiếp theo của phần tử cuối cùng là phần tử đầu tiên của mảng thường được gọi là hình tròn.

Rõ ràng là không tồn tại cơ chế lưu trữ dữ liệu như thế này, dữ liệu sẽ vẫn được lưu trữ trong các khối bộ nhớ liên tục và mảng tròn giống như một ý tưởng hơn là thực tế.

Vấn đề

Chúng tôi được yêu cầu viết một hàm JavaScript lấy một mảng tròn các Số nguyên, arr, làm đối số đầu tiên và duy nhất.

Sau đó, hàm sẽ tạo và trả về một mảng có chứa phần tử lớn hơn tiếp theo cho mỗi phần tử tương ứng của mảng ban đầu. Số Lớn hơn Tiếp theo của một số, chẳng hạn như num, là số lớn hơn đầu tiên theo thứ tự đi ngang của nó (ngay trong trường hợp của chúng ta) tiếp theo trong mảng, có nghĩa là chúng ta có thể tìm kiếm theo hình tròn để tìm số lớn hơn tiếp theo của nó. Nếu điều đó không tồn tại, chúng ta nên xem xét -1 cho số này.

Ví dụ:nếu đầu vào của hàm là -

const arr = [7, 8, 7];

Sau đó, kết quả đầu ra phải là -

const output = [8, -1, 8];

Giải thích đầu ra

Số lớn hơn tiếp theo của cả 7 trong mảng là 8 và vì mảng là hình tròn nhưng với 8, không có phần tử nào lớn hơn, do đó chúng tôi đặt -1 cho nó.

Ví dụ

Mã cho điều này sẽ là -

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 mã:

Trong khi lặp qua mảng nếu chúng tôi tìm thấy một phần tử lớn hơn một phần tử trong ngăn xếp, chúng tôi đặt res [small] thành phần tử lớn hơn hiện tại được tìm thấy.

Bây giờ, chúng ta lại bắt đầu từ đầu arr và xử lý các phần tử mà chúng ta không thể tìm thấy phần tử lớn hơn tiếp theo trong vòng lặp for trước đó. Cuối cùng, vẫn sẽ có một số yếu tố mà không có yếu tố nào lớn hơn tiếp theo.

Đầu ra

Và đầu ra trong bảng điều khiển sẽ là -

[8, -1, 8]