function maxArea(height: number[]): number {
    let l = 0;
    let r = height.length - 1;
    let best = 0;

    while (l < r) {
        const h = Math.min(height[l], height[r]);
        best = Math.max(best, h * (r - l));

        // 移动较短的一边，才可能找到更大的面积
        if (height[l] < height[r]) {
            l++;
        } else {
            r--;
        }
    }

    return best;
}

console.log(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7])); // 49

function curry(fn: Function) {
    return function curried(this: any, ...args: any[]): any {
        if (args.length >= fn.length) {
            return fn.apply(this, args);
        }
        return (...rest: any[]) => curried.apply(this, [...args, ...rest]);
    };
}

const add = (a: number, b: number, c: number) => a + b + c;
const curriedAdd = curry(add);
console.log(curriedAdd(1)(2)(3));   // 6
console.log(curriedAdd(1, 2)(3));   // 6

const _ = Symbol("placeholder");

function curryWithPlaceholder(fn: Function): any {
    const judge = (...args: any[]): any =>
        // 非占位符参数足够时执行
        args.length >= fn.length &&
        args.slice(0, fn.length).every((a) => a !== _)
            ? fn(...args.filter((a) => a !== _))
            : (arg: any, ...rest: any[]) => judge(...replace(args, arg), ...rest);

    // 用新传入的 arg 填补 args 中第一个占位符；没有则追加
    function replace(args: any[], arg: any): any[] {
        const idx = args.indexOf(_);
        if (idx !== -1 && arg !== _) {
            const copy = [...args];
            copy[idx] = arg;
            return copy;
        }
        return [...args, arg];
    }

    return judge;
}

const sum3 = (a: number, b: number, c: number) => a + b + c;
const c3 = curryWithPlaceholder(sum3);
console.log(c3(_, 2)(1)(3));   // 6
console.log(c3(1, _, 3)(2));   // 6
console.log(c3(1)(2)(3));      // 6

// 暴露占位符
curryWithPlaceholder._ = _;

function myInstanceof(left: any, right: any): boolean {
    // 原始值 / null / undefined 直接 false
    if (left === null || (typeof left !== "object" && typeof left !== "function")) {
        return false;
    }

    // 支持 Symbol.hasInstance（对齐原生优先级）
    const hasInstance = right[Symbol.hasInstance];
    if (typeof hasInstance === "function") {
        return !!hasInstance.call(right, left);
    }

    if (typeof right !== "function") {
        throw new TypeError("Right-hand side of 'instanceof' is not callable");
    }

    const proto = right.prototype; // 要找的目标
    let cursor = Object.getPrototypeOf(left);

    while (cursor !== null) {
        if (cursor === proto) return true;
        cursor = Object.getPrototypeOf(cursor); // 沿原型链上溯
    }

    return false;
}

// 测试
class Animal {}
class Dog extends Animal {}

console.log(myInstanceof(new Dog(), Dog));     // true
console.log(myInstanceof(new Dog(), Animal));  // true（继承链）
console.log(myInstanceof(new Dog(), Object));  // true
console.log(myInstanceof("str", String));      // false（原始值）
console.log(myInstanceof(new String("s"), String)); // true

// myCall
Function.prototype.myCall = function (this: Function, thisArg?: any, ...args: any[]): any {
    const ctx = thisArg == null ? globalThis : Object(thisArg);
    const key = Symbol("fn");
    (ctx as any)[key] = this; // this 即调用者函数
    const result = (ctx as any)[key](...args);
    delete (ctx as any)[key];
    return result;
};

// myApply
Function.prototype.myApply = function (this: Function, thisArg?: any, argsList?: any[]): any {
    const ctx = thisArg == null ? globalThis : Object(thisArg);
    const key = Symbol("fn");
    (ctx as any)[key] = this;
    const result = argsList
        ? (ctx as any)[key](...argsList)
        : (ctx as any)[key]();
    delete (ctx as any)[key];
    return result;
};

// myBind
Function.prototype.myBind = function (this: Function, thisArg?: any, ...boundArgs: any[]): Function {
    const original = this;

    // 用一个空函数承接原型链，保证 new bound() 能拿到 original.prototype
    const bound = function (this: any, ...callArgs: any[]): any {
        const allArgs = [...boundArgs, ...callArgs]; // 柯里化：预置参数在前
        // 被 new 调用时 this 是新建实例，忽略绑定的 thisArg
        const wasNew = new.target !== undefined;
        if (wasNew) {
            return new (original as any)(...allArgs);
        }
        return original.apply(thisArg, allArgs);
    };

    if (original.prototype) {
        bound.prototype = Object.create(original.prototype);
    }
    return bound;
};

// 测试
const obj = { name: "jack" };
function greet(this: any, a: string, b: string) {
    return `${a} ${this.name} ${b}`;
}

console.log(greet.myCall(obj, "hi", "!"));          // "hi jack !"
console.log(greet.myApply(obj, ["hello", "?"]));    // "hello jack ?"

const boundGreet = greet.myBind(obj, "hey");
console.log(boundGreet("there"));                   // "hey jack there"

function deepClone<T>(source: T, cache = new WeakMap<object, any>()): T {
    // 原始值 / null / 函数：直接返回
    if (source === null || typeof source !== "object") {
        return source;
    }

    // 命中缓存：处理循环引用的关键
    if (cache.has(source as object)) {
        return cache.get(source as object);
    }

    // Date
    if (source instanceof Date) {
        return new Date(source.getTime()) as unknown as T;
    }

    // RegExp
    if (source instanceof RegExp) {
        return new RegExp(source.source, source.flags) as unknown as T;
    }

    // Map
    if (source instanceof Map) {
        const result = new Map();
        cache.set(source as object, result);
        for (const [key, value] of source.entries()) {
            result.set(deepClone(key, cache), deepClone(value, cache));
        }
        return result as unknown as T;
    }

    // Set
    if (source instanceof Set) {
        const result = new Set();
        cache.set(source as object, result);
        for (const value of source.values()) {
            result.add(deepClone(value, cache));
        }
        return result as unknown as T;
    }

    // 数组
    if (Array.isArray(source)) {
        const result: any[] = [];
        cache.set(source as object, result);
        for (let i = 0; i < source.length; i++) {
            result[i] = deepClone(source[i], cache);
        }
        return result as unknown as T;
    }

    // 普通对象（含 Symbol key）
    const result = Object.create(Object.getPrototypeOf(source));
    cache.set(source as object, result); // 先建立映射再递归，才能扛住循环引用
    for (const key of Reflect.ownKeys(source)) {
        const descriptor = Object.getOwnPropertyDescriptor(source, key)!;
        if (descriptor.enumerable) {
            result[key] = deepClone((source as any)[key], cache);
        } else {
            Object.defineProperty(result, key, descriptor);
        }
    }
    return result as T;
}

// 测试
const obj: any = { name: "jack", tags: ["ts", "algo"], born: new Date(0) };
obj.self = obj;
const copy = deepClone(obj);
console.log(copy.self === copy);        // true
console.log(copy.tags !== obj.tags);    // true（独立副本）

function promiseRace<T>(
    iterables: Iterable<T | PromiseLike<T>>
): Promise<Awaited<T>> {
    return new Promise((resolve, reject) => {
        for (const item of iterables) {
            // 用 Promise.resolve 包装，普通值也异步参与竞争
            Promise.resolve(item).then(resolve, reject);
        }
        // 空集合：循环不执行，Promise 永久 pending（与原生一致）
    });
}

// 测试
const slow = (v: string, ms: number) =>
    new Promise<string>((r) => setTimeout(() => r(v), ms));
const fastFail = (ms: number) =>
    new Promise<never>((_, rej) => setTimeout(() => rej("boom"), ms));

promiseRace([slow("slow-win", 300), fastFail(100)])
    .then(console.log)
    .catch(console.log); // "boom"（先 settle）

promiseRace([slow("first", 50), slow("second", 200)])
    .then(console.log);  // "first"

type Status = "pending" | "fulfilled" | "rejected";

class MyPromise {
    private status: Status = "pending";
    private value: any = undefined;
    private reason: any = undefined;

    constructor(executor: (resolve: (v?: any) => void, reject: (r?: any) => void) => void) {
        try {
            executor(this.resolve.bind(this), this.reject.bind(this));
        } catch (e) {
            this.reject(e);
        }
    }

    private resolve(value: any): void {
        if (this.status !== "pending") return; // 只允许一次
        // resolve 了一个 thenable -> 采用其状态
        if (value && (typeof value === "object" || typeof value === "function")
            && typeof value.then === "function") {
            value.then(this.resolve.bind(this), this.reject.bind(this));
            return;
        }
        this.status = "fulfilled";
        this.value = value;
    }

    private reject(reason: any): void {
        if (this.status !== "pending") return;
        this.status = "rejected";
        this.reason = reason;
    }

    then(onFulfilled?: any, onRejected?: any): MyPromise {
        // 值穿透：非函数用默认处理器
        onFulfilled = typeof onFulfilled === "function" ? onFulfilled : (v: any) => v;
        onRejected = typeof onRejected === "function" ? onRejected : (e: any) => { throw e; };

        return new MyPromise((resolve, reject) => {
            const runFulfilled = () =>
                queueMicrotask(() => {
                    try { resolve(onFulfilled(this.value)); }
                    catch (e) { reject(e); }
                });
            const runRejected = () =>
                queueMicrotask(() => {
                    try { resolve(onRejected(this.reason)); }
                    catch (e) { reject(e); }
                });

            if (this.status === "fulfilled") {
                runFulfilled();
            } else if (this.status === "rejected") {
                runRejected();
            }
            // 注意：简易版未处理 pending 时回调的收集；
            // 完整版应把 runFulfilled/runRejected 存入回调数组，resolve/reject 时再依次触发。
        });
    }

    catch(onRejected: any): MyPromise {
        return this.then(undefined, onRejected);
    }

    static resolve(v: any): MyPromise {
        if (v instanceof MyPromise) return v;
        return new MyPromise((resolve) => resolve(v));
    }
}

// 测试：链式 + 值穿透
new MyPromise<number>((resolve) => setTimeout(() => resolve(1), 50))
    .then((v) => { console.log(v); return v + 1; }) // 1
    .then(null)                                    // 值穿透
    .then((v) => console.log(v));                  // 2

function buildLPS(pattern: string): number[] {
    const n = pattern.length;
    const lps = new Array(n).fill(0);
    let len = 0; // 前一个最长前后缀长度
    let i = 1;

    while (i < n) {
        if (pattern[i] === pattern[len]) {
            lps[i++] = ++len;
        } else if (len > 0) {
            len = lps[len - 1]; // 回溯，i 不前进
        } else {
            lps[i++] = 0;
        }
    }
    return lps;
}

function strStr(haystack: string, needle: string): number {
    const m = haystack.length;
    const n = needle.length;
    if (n === 0) return 0;

    const lps = buildLPS(needle);
    let i = 0; // haystack 指针（永不回退）
    let j = 0; // needle 指针

    while (i < m) {
        if (haystack[i] === needle[j]) {
            i++;
            j++;
            if (j === n) return i - j; // 完全匹配
        } else if (j > 0) {
            j = lps[j - 1]; // 部分匹配，跳回
        } else {
            i++; // j=0 直接前移
        }
    }
    return -1;
}

console.log(strStr("sadbutsad", "sad"));       // 0
console.log(strStr("ababcababc", "abc"));       // 2
console.log(strStr("leetcode", "leeto"));       // -1
console.log(buildLPS("abab"));                  // [0,0,1,2]

// 2.3 快速选择（原地，平均 O(n)）
function findKthLargest(nums: number[], k: number): number {
    const target = nums.length - k; // 转成升序下标

    function partition(lo: number, hi: number): number {
        // 随机化，避免有序退化
        const rand = lo + Math.floor(Math.random() * (hi - lo + 1));
        [nums[rand], nums[hi]] = [nums[hi], nums[rand]];
        const pivot = nums[hi];
        let i = lo;
        for (let j = lo; j < hi; j++) {
            if (nums[j] < pivot) {
                [nums[i], nums[j]] = [nums[j], nums[i]];
                i++;
            }
        }
        [nums[i], nums[hi]] = [nums[hi], nums[i]];
        return i;
    }

    let lo = 0;
    let hi = nums.length - 1;
    while (true) {
        const p = partition(lo, hi);
        if (p === target) return nums[p];
        if (p < target) lo = p + 1;
        else hi = p - 1;
    }
}

// 2.2 最小堆版（适合数据流 / 海量 TopK）
// 借助一个数值小顶堆：这里用极简实现演示思路
class MinHeap {
    private h: number[] = [];
    get size() { return this.h.length; }
    peek() { return this.h[0]; }
    push(v: number) {
        const h = this.h;
        h.push(v);
        let i = h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (h[p] <= h[i]) break;
            [h[p], h[i]] = [h[i], h[p]];
            i = p;
        }
    }
    pop() {
        const h = this.h;
        const top = h[0];
        const last = h.pop()!;
        if (h.length) {
            h[0] = last;
            let i = 0;
            while (true) {
                const l = 2 * i + 1;
                const r = 2 * i + 2;
                let s = i;
                if (l < h.length && h[l] < h[s]) s = l;
                if (r < h.length && h[r] < h[s]) s = r;
                if (s === i) break;
                [h[s], h[i]] = [h[i], h[s]];
                i = s;
            }
        }
        return top;
    }
}

function topKKthLargest(nums: number[], k: number): number {
    const heap = new MinHeap();
    for (const x of nums) {
        if (heap.size < k) heap.push(x);
        else if (x > heap.peek()) {
            heap.pop();
            heap.push(x);
        }
    }
    return heap.peek();
}

console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2));     // 5
console.log(topKKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)); // 4

function numIslands(grid: string[][]): number {
    if (grid.length === 0) return 0;
    const m = grid.length;
    const n = grid[0].length;

    // DFS 淹没整座岛
    function sink(r: number, c: number): void {
        if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] !== "1") {
            return;
        }
        grid[r][c] = "0"; // 标记已访问（淹掉）
        sink(r + 1, c);
        sink(r - 1, c);
        sink(r, c + 1);
        sink(r, c - 1);
    }

    let count = 0;
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (grid[r][c] === "1") {
                count++;
                sink(r, c);
            }
        }
    }
    return count;
}

// BFS 版（防止超深网格递归爆栈）
function numIslandsBFS(grid: string[][]): number {
    const m = grid.length;
    const n = grid[0].length;
    const dirs = [
        [1, 0], [-1, 0], [0, 1], [0, -1],
    ];
    let count = 0;

    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (grid[r][c] !== "1") continue;
            count++;
            grid[r][c] = "0";
            const queue: [number, number][] = [[r, c]];
            while (queue.length) {
                const [x, y] = queue.shift()!;
                for (const [dx, dy] of dirs) {
                    const nx = x + dx;
                    const ny = y + dy;
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] === "1") {
                        grid[nx][ny] = "0";
                        queue.push([nx, ny]);
                    }
                }
            }
        }
    }
    return count;
}