Kiểm tra mảng gần như tăng dần (bỏ tối đa 1 phần tử) trong JavaScript

Mô tả bài toán

Cho mảng số, kiểm tra có thể bỏ tối đa 1 phần tử để mảng còn lại tăng nghiêm ngặt (strictly increasing) không.

Ví dụ minh họa

const arr1 = [3, 5, 67, 98, 3];
const arr2 = [4, 3, 5, 67, 98, 3];

const almostIncreasingSequence = sequence => {
  let removed = 0;
  let i = 0;
  let prev = -Infinity;
  while (removed < 2 && i < sequence.length) {
    if (sequence[i] > prev) {
      prev = sequence[i];
    } else {
      prev = Math.min(prev, sequence[i]);
      removed++;
    }
    i++;
  }
  return removed < 2;
};

console.log(almostIncreasingSequence(arr1)); // true
console.log(almostIncreasingSequence(arr2)); // false

Kết quả

true false

Giải thích thuật toán

Duyệt một lần, theo dõi prev (giá trị hợp lệ cuối). Nếu phần tử hiện tại <= prev, coi như "bỏ" nó (tăng removed), cập nhật prev = min(prev, current) để tối ưu cho phần tử sau.

Độ phức tạp

O(n) time, O(1) space - tối ưu.