// 基础版：精确匹配
function search(nums: number[], target: number): number {
    let left = 0;
    let right = nums.length - 1; // 左闭右闭

    while (left <= right) {
        const mid = left + ((right - left) >> 1);
        if (nums[mid] === target) return mid;
        if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

// 找第一个 >= target 的下标（可能返回 nums.length）
function lowerBound(nums: number[], target: number): number {
    let left = 0;
    let right = nums.length; // 左闭右开 [left, right)
    while (left < right) {
        const mid = left + ((right - left) >> 1);
        if (nums[mid] < target) left = mid + 1;
        else right = mid; // mid 可能是答案，保留
    }
    return left;
}

// 找第一个 > target 的下标
function upperBound(nums: number[], target: number): number {
    let left = 0;
    let right = nums.length;
    while (left < right) {
        const mid = left + ((right - left) >> 1);
        if (nums[mid] <= target) left = mid + 1;
        else right = mid;
    }
    return left;
}

function searchRange(nums: number[], target: number): number[] {
    const lo = lowerBound(nums, target);
    // lo 越界或值不等，说明不存在
    if (lo === nums.length || nums[lo] !== target) return [-1, -1];
    return [lo, upperBound(nums, target) - 1];
}

console.log(searchRange([5, 7, 7, 8, 8, 10], 8)); // [3, 4]
console.log(searchRange([5, 7, 7, 8, 8, 10], 6)); // [-1, -1]

function coinChange(coins: number[], amount: number): number {
    const dp = new Array(amount + 1).fill(amount + 1); // 视作 +∞
    dp[0] = 0;

    for (let i = 1; i <= amount; i++) {
        for (const c of coins) {
            if (c <= i) {
                dp[i] = Math.min(dp[i], dp[i - c] + 1);
            }
        }
    }

    return dp[amount] > amount ? -1 : dp[amount];
}

console.log(coinChange([1, 2, 5], 11)); // 3
console.log(coinChange([2], 3));        // -1
console.log(coinChange([1, 3, 4], 6));  // 2

// 2.1 DP：O(n²)
function lengthOfLIS(nums: number[]): number {
    const n = nums.length;
    const dp = new Array(n).fill(1);
    let ans = 1;

    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        ans = Math.max(ans, dp[i]);
    }
    return ans;
}

// 2.2 贪心 + 二分：O(n log n)
function lengthOfLISNLogN(nums: number[]): number {
    const tails: number[] = [];

    for (const x of nums) {
        // 二分找第一个 >= x 的下标（lowerBound）
        let lo = 0;
        let hi = tails.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (tails[mid] < x) lo = mid + 1;
            else hi = mid;
        }

        if (lo === tails.length) tails.push(x); // x 最大，延长
        else tails[lo] = x;                       // 替换，压小结尾
    }

    return tails.length;
}

console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])); // 4
console.log(lengthOfLISNLogN([0, 1, 0, 3, 2, 3]));       // 4

// 滚动变量（最优：O(n) 时间 / O(1) 空间）
function climbStairs(n: number): number {
    if (n <= 2) return n;
    let prev = 1; // f(i-2)
    let curr = 2; // f(i-1)
    for (let i = 3; i <= n; i++) {
        const next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

// 记忆化递归（自顶向下）
function climbStairsMemo(n: number, memo: Map<number, number> = new Map()): number {
    if (n <= 2) return n;
    if (memo.has(n)) return memo.get(n)!;
    const res = climbStairsMemo(n - 1, memo) + climbStairsMemo(n - 2, memo);
    memo.set(n, res);
    return res;
}

console.log(climbStairs(3)); // 3
console.log(climbStairs(5)); // 8

function lowestCommonAncestor(
    root: TreeNode | null,
    p: TreeNode,
    q: TreeNode
): TreeNode | null {
    if (root === null || root === p || root === q) return root;

    const left = lowestCommonAncestor(root.left, p, q);
    const right = lowestCommonAncestor(root.right, p, q);

    // p、q 分居两侧，当前节点即最近公共祖先
    if (left !== null && right !== null) return root;
    // 否则返回非空的那一侧
    return left !== null ? left : right;
}

// BST 版本
function lowestCommonAncestorBST(
    root: TreeNode | null,
    p: TreeNode,
    q: TreeNode
): TreeNode | null {
    let curr = root;
    while (curr) {
        if (p.val < curr.val && q.val < curr.val) {
            curr = curr.left;
        } else if (p.val > curr.val && q.val > curr.val) {
            curr = curr.right;
        } else {
            return curr; // 分裂点或命中其一
        }
    }
    return null;
}

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val ?? 0;
        this.left = left ?? null;
        this.right = right ?? null;
    }
}

// 前序：根 -> 左 -> 右
function preorder(root: TreeNode | null): number[] {
    const res: number[] = [];
    if (!root) return res;
    const stack: TreeNode[] = [root];

    while (stack.length) {
        const node = stack.pop()!;
        res.push(node.val);                 // 访问根
        if (node.right) stack.push(node.right); // 先压右
        if (node.left) stack.push(node.left);   // 再压左，保证左先弹出
    }
    return res;
}

// 中序：左 -> 根 -> 右
function inorder(root: TreeNode | null): number[] {
    const res: number[] = [];
    const stack: TreeNode[] = [];
    let curr = root;

    while (curr || stack.length) {
        while (curr) {         // 一路向左压栈
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop()!;   // 弹出最左节点
        res.push(curr.val);    // 访问根
        curr = curr.right;     // 转向右子树
    }
    return res;
}

// 后序：左 -> 右 -> 根（用「根右左 + 反转」）
function postorder(root: TreeNode | null): number[] {
    const res: number[] = [];
    if (!root) return res;
    const stack: TreeNode[] = [root];

    while (stack.length) {
        const node = stack.pop()!;
        res.push(node.val);                // 根
        if (node.left) stack.push(node.left);  // 先压左
        if (node.right) stack.push(node.right); // 再压右，得到「根右左」
    }
    return res.reverse();                  // 反转为「左右根」
}

console.log(preorder(new TreeNode(1, null, new TreeNode(2, new TreeNode(3)))));
// [1,2,3]
console.log(postorder(new TreeNode(1, null, new TreeNode(2, new TreeNode(3)))));
// [3,2,1]

function detectCycle(head: ListNode | null): ListNode | null {
    let slow = head;
    let fast = head;

    // 阶段一：判断是否有环，找到相遇点
    while (fast !== null && fast.next !== null) {
        slow = slow!.next;
        fast = fast.next.next;
        if (slow === fast) {
            // 阶段二：一个指针回头，同速前进，再相遇即入口
            let p = head;
            while (p !== slow) {
                p = p!.next;
                slow = slow!.next;
            }
            return p;
        }
    }

    return null; // 无环
}

class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = val ?? 0;
        this.next = next ?? null;
    }
}

function hasCycle(head: ListNode | null): boolean {
    let slow = head;
    let fast = head;

    while (fast !== null && fast.next !== null) {
        slow = slow!.next;           // 走一步
        fast = fast.next.next;       // 走两步

        if (slow === fast) return true; // 相遇即有环
    }

    return false; // fast 到头，无环
}

// 测试：构造 3 -> 2 -> 0 -> -4 -> (回到 2)
const n = new ListNode(3, new ListNode(2, new ListNode(0, new ListNode(-4))));
n.next.next.next.next = n.next; // 造环
console.log(hasCycle(n)); // true
console.log(hasCycle(new ListNode(1))); // false

function promiseAll<T>(
    iterables: Iterable<T | PromiseLike<T>>
): Promise<Awaited<T>[]> {
    return new Promise((resolve, reject) => {
        const promises = Array.from(iterables);
        const n = promises.length;
        const results = new Array(n);
        let completed = 0;

        if (n === 0) {
            resolve(results as Awaited<T>[]);
            return;
        }

        for (let i = 0; i < n; i++) {
            // 用 Promise.resolve 兼容非 Promise 值
            Promise.resolve(promises[i]).then(
                (value) => {
                    results[i] = value; // 按下标写入，保证顺序
                    completed++;
                    if (completed === n) {
                        resolve(results as Awaited<T>[]);
                    }
                },
                (reason) => {
                    reject(reason); // 快速失败
                }
            );
        }
    });
}

// 测试
promiseAll([1, Promise.resolve(2), new Promise((r) => setTimeout(() => r(3), 100))])
    .then(console.log); // [1, 2, 3]

promiseAll([Promise.resolve("a"), Promise.reject("boom"), Promise.resolve("c")])
    .catch(console.log); // "boom"

function throttleTimestamp<T extends (...args: any[]) => void>(
    fn: T,
    wait: number
) {
    let last = 0;
    return function (this: any, ...args: Parameters<T>) {
        const now = Date.now();
        if (now - last >= wait) {
            last = now;
            fn.apply(this, args);
        }
    };
}

function throttleTimer<T extends (...args: any[]) => void>(
    fn: T,
    wait: number
) {
    let timer: ReturnType<typeof setTimeout> | null = null;
    return function (this: any, ...args: Parameters<T>) {
        if (timer !== null) return; // 执行中，丢弃
        timer = setTimeout(() => {
            timer = null;
            fn.apply(this, args);
        }, wait);
    };
}

function throttle<T extends (...args: any[]) => void>(fn: T, wait: number) {
    let timer: ReturnType<typeof setTimeout> | null = null;
    let last = 0;

    return function (this: any, ...args: Parameters<T>) {
        const now = Date.now();
        const remaining = wait - (now - last);

        if (remaining <= 0) {
            // 到点了：立即执行
            if (timer !== null) {
                clearTimeout(timer);
                timer = null;
            }
            last = now;
            fn.apply(this, args);
        } else if (timer === null) {
            // 没到点且没有排队：挂一个定时器保证最后一次执行
            timer = setTimeout(() => {
                last = Date.now();
                timer = null;
                fn.apply(this, args);
            }, remaining);
        }
    };
}

// 用法
const onScroll = throttle(() => console.log("handle scroll"), 200);
window.addEventListener("scroll", onScroll);