การหา Subarray ของค่าที่มากกว่าค่าทั้งหมดทางขวาใน JavaScript

ภาพรวม

บทความนี้สาธิตวิธีหา Element ในอาร์เรย์ที่มีค่ามากกว่าค่าทั้งหมดทางด้านขวา (Right Side) เรียกว่า "Leaders" หรือ "Right-to-Left Maxima"

ตัวอย่าง

Input:  [12, 45, 6, 4, 23, 23, 21, 1]
Output: [1, 21, 23, 45] (จากขวาไปซ้าย)
// 1: มากกว่าทางขวา (ไม่มี) -> ✓
// 21: มากกว่า 1 -> ✓
// 23: มากกว่า 21, 1 -> ✓
// 23 (ตัวแรก): ไม่มากกว่า 23 (ตัวที่สอง) -> ✗
// 45: มากกว่า 23, 21, 1 -> ✓

การนำไปใช้ (ReduceRight)

const largerThanRight = (arr = []) => {
  const creds = arr.reduceRight((acc, val) => {
    let { largest, res } = acc;
    if (val > largest) {
      res.push(val);
      largest = val;
    }
    return { largest, res };
  }, { largest: -Infinity, res: [] });
  
  return creds.res; // อยู่ในลำดับขวาไปซ้าย
};

console.log(largerThanRight([12, 45, 6, 4, 23, 23, 21, 1]));

ผลลัพธ์

[1, 21, 23, 45]

วิธีการ Iterative (เข้าใจง่ายกว่า)

const findLeaders = (arr) => {
  const leaders = [];
  let maxSoFar = -Infinity;
  
  // วนจากขวาไปซ้าย
  for (let i = arr.length - 1; i >= 0; i--) {
    if (arr[i] > maxSoFar) {
      leaders.push(arr[i]);
      maxSoFar = arr[i];
    }
  }
  
  return leaders.reverse(); // กลับลำดับเป็นซ้ายไปขวา
};

กรณีพิเศษ: รวมค่าเท่ากัน (>=)

const findLeadersInclusive = (arr) => {
  const leaders = [];
  let maxSoFar = -Infinity;
  
  for (let i = arr.length - 1; i >= 0; i--) {
    if (arr[i] >= maxSoFar) { // >= แทน >
      leaders.push(arr[i]);
      maxSoFar = arr[i];
    }
  }
  return leaders.reverse();
};

// [12, 45, 6, 4, 23, 23, 21, 1] -> [1, 21, 23, 23, 45]

การประยุกต์ใช้

• Stock Trading: หาวันที่ราคาสูงสุดจากวันนั้นไปจนจบ (Peak Detection)
• Algorithm: Next Greater Element Problem
• Data Streaming: Online Maximum Tracking
• Computational Geometry: Skyline Problem

Complexity

• Time: O(n) - Single Pass
• Space: O(k) - k = จำนวน Leaders (worst case O(n) เมื่อเรียงลดลง)