การตรวจสอบ Increasing Triplet Subsequence ใน JavaScript

Increasing Numbers

ลำดับที่แต่ละ element >= element ก่อนหน้า

ปัญหา

ตรวจสอบว่ามี increasing triplet (i < j < k, arr[i] < arr[j] < arr[k]) ในอาร์เรย์หรือไม่

ตัวอย่าง

arr = [4, 1, 5, 7, 3, 1, 4] -> true (1,5,7)

ตัวอย่างโค้ด

const arr = [4, 1, 5, 7, 3, 1, 4];

const increasingTriplet = function(arr) {
  let first = Infinity;
  let second = Infinity;
  for (let curr of arr) {
    if (curr > second && curr > first) {
      return true;
    }
    if (curr > first) {
      second = curr;
    } else {
      first = curr;
    }
  }
  return false;
};

console.log(increasingTriplet(arr));

ผลลัพธ์

true

คำอธิบาย

Gready: first = ตัวเลขน้อยที่สุดที่เจอมา, second = ตัวเลขน้อยที่สุดที่มากกว่า first

หากเจอ curr > second -> พบ triplet (first, second, curr)

Time: O(n), Space: O(1)

หมายเหตุ: โค้ดตรวจสอบ strictly increasing (arr[i] < arr[j] < arr[k])