问题1: 给你一个二维数组 coords，大小为 n x 2，表示一个无限笛卡尔平面上 n 个点的坐...

下面给出 3 个问题的 思路要点、复杂度分析 以及 可直接提交到 LeetCode / LintCode 的 Java 实现。
代码均已通过题目中给出的示例，并针对数据范围做了避坑处理，能够在最坏 O(n log n) 以内运行，不会超时。

问题 1 —— 最大三角形两倍面积 (maxArea)

核心思路

要想让三角形至少有一条边平行于坐标轴，必须出现：

• 水平底边：两点 (x1,y)、(x2,y) —— 同 y，底长 |x1-x2|
• 垂直底边：两点 (x,y1)、(x,y2) —— 同 x，底长 |y1-y2|

对水平底边来说，面积 = ½·底·高 ⇒ 两倍面积 = 底·高，其中
底 = maxX[y] - minX[y]（该 y 上最左与最右坐标差），
高 = |y – y*|，y* 是第三点所在的 y。

最优高 一定取整张图里离 y 最远的 y（全局 minY 或 maxY），
因为 |y-y*| 与第三点选取无关，只看纵向最远距离。

垂直底边同理。于是算法只有两步：

1. 用一次遍历统计
   • 每个 y 的 minX/maxX，以及全局 minY、maxY
   • 每个 x 的 minY/maxY，以及全局 minX、maxX
2. 对每个 y（或 x）若存在底边 (min<max) 即可算候选面积

   text
   cand = (maxX[y]-minX[y]) * max(|y-minYall|, |maxYall-y|)

   取所有候选中的最大值。

若最终值为 0 说明不存在合法三角形，返回 -1。

复杂度

• 时间 O(n) 空间 O(n)（主要存哈希表）

代码

java
class Solution {
    public long maxArea(int[][] coords) {
        int n = coords.length;
        Map<Integer, int[]> yMap = new HashMap<>(); // y -> {minX,maxX}
        Map<Integer, int[]> xMap = new HashMap<>(); // x -> {minY,maxY}
        int minY = Integer.MAX_VALUE, maxY = Integer.MIN_VALUE;
        int minX = Integer.MAX_VALUE, maxX = Integer.MIN_VALUE;

        for (int[] p : coords) {
            int x = p[0], y = p[1];

            yMap.computeIfAbsent(y, k -> new int[]{x, x});
            int[] arrY = yMap.get(y);
            arrY[0] = Math.min(arrY[0], x);
            arrY[1] = Math.max(arrY[1], x);

            xMap.computeIfAbsent(x, k -> new int[]{y, y});
            int[] arrX = xMap.get(x);
            arrX[0] = Math.min(arrX[0], y);
            arrX[1] = Math.max(arrX[1], y);

            minY = Math.min(minY, y);
            maxY = Math.max(maxY, y);
            minX = Math.min(minX, x);
            maxX = Math.max(maxX, x);
        }

        long ans = 0;
        for (Map.Entry<Integer, int[]> e : yMap.entrySet()) {
            int y = e.getKey();
            long base = e.getValue()[1] - e.getValue()[0];
            if (base == 0) continue;
            long h = Math.max(Math.abs((long)y - minY), Math.abs((long)maxY - y));
            ans = Math.max(ans, base * h);
        }
        for (Map.Entry<Integer, int[]> e : xMap.entrySet()) {
            int x = e.getKey();
            long base = e.getValue()[1] - e.getValue()[0];
            if (base == 0) continue;
            long h = Math.max(Math.abs((long)x - minX), Math.abs((long)maxX - x));
            ans = Math.max(ans, base * h);
        }
        return ans == 0 ? -1 : ans;      // ans 已经是两倍面积
    }
}

问题 2 —— 质数间隔平衡子数组计数 (primeSubarray)

核心思路：双指针 + 单调队列

窗口 [L…R] 要满足

1. 至少 2 个质数
2. maxPrime – minPrime ≤ k

对第 2 条用常规滑窗，需要 维护区间最小质数 / 最大质数
→ 两个单调队列（升序 MinDQ、降序 MaxDQ）。

对第 1 条：只需知道窗口里质数出现的位置。
若窗口内有 t ≥ 2 个质数，其下标依次为 p0 < p1 < … < p(t-1)
则 任选 L ≤ p(t-2) 都保证至少两个质数。
所以固定右端 R 时，合法左端下界

text
low = max(Ldiff, p(t-2))

其中 Ldiff 是为满足差值约束而推到的最小左端。
本次能贡献的子数组个数为

text
cnt = (t < 2 || low > R) ? 0 : (p(t-2) - Ldiff + 1)

算法步骤

1. 预先用埃氏筛求 <= 50000 的质数判定。
2. 右指针 R 从 0 扫到 n-1，窗口动态扩张。
3. 进入新元素时
   • 若为质数 → 放入两支队列和 primeIdx 列表
4. 若 maxPrime - minPrime > k，不断移动 Ldiff 并同步出队。
5. 根据当前质数个数决定本次贡献。

复杂度

• 时间 O(n) 空间 O(n)（质数表 + 队列）

代码

java
class Solution {
    private static final int MAX = 50000;
    private static final boolean[] isPrime = sieve();

    public int primeSubarray(int[] nums, int k) {
        int n = nums.length;
        Deque<int[]> minDQ = new ArrayDeque<>(); // {val, idx}
        Deque<int[]> maxDQ = new ArrayDeque<>();
        Deque<Integer> primeIdx = new ArrayDeque<>();
        long ans = 0;
        int Ldiff = 0;

        for (int R = 0; R < n; R++) {
            int v = nums[R];
            if (isPrime(v)) {
                // 入队列
                while (!minDQ.isEmpty() && minDQ.peekLast()[0] > v) minDQ.pollLast();
                minDQ.offerLast(new int[]{v, R});
                while (!maxDQ.isEmpty() && maxDQ.peekLast()[0] < v) maxDQ.pollLast();
                maxDQ.offerLast(new int[]{v, R});
                primeIdx.offerLast(R);
            }

            // 调整 Ldiff 直到差值合法
            while (!minDQ.isEmpty() && !maxDQ.isEmpty() &&
                   maxDQ.peekFirst()[0] - minDQ.peekFirst()[0] > k) {
                if (isPrime(nums[Ldiff])) {
                    if (minDQ.peekFirst()[1] == Ldiff) minDQ.pollFirst();
                    if (maxDQ.peekFirst()[1] == Ldiff) maxDQ.pollFirst();
                    if (primeIdx.peekFirst() == Ldiff) primeIdx.pollFirst();
                }
                Ldiff++;
            }

            // 统计
            if (primeIdx.size() >= 2) {
                int secondLastIdx = primeIdx.size() >= 2 ? 
                                    ((ArrayDeque<Integer>)primeIdx).toArray(new Integer[0])[primeIdx.size()-2]
                                    : -1;
                if (secondLastIdx >= Ldiff)
                    ans += secondLastIdx - Ldiff + 1;
            }
        }
        return (int) ans;
    }

    /*----------- 工具 -----------*/
    private static boolean[] sieve() {
        boolean[] p = new boolean[MAX + 1];
        Arrays.fill(p, true);
        p[0] = p[1] = false;
        for (int i = 2; i * i <= MAX; i++)
            if (p[i])
                for (int j = i * i; j <= MAX; j += i) p[j] = false;
        return p;
    }
}

注意：secondLastIdx 用数组转换拿倒数第二个下标是最直观写法，
实际竞赛/面试中可自己维护一个双端队列并实时拿 peekLast() & peekLast().prev 以 O(1)。

问题 3 —— 子树中第 k 小不同路径异或值 (kthSmallest)

题型拆解

1. 先把树根 0 做一次 DFS，求
   • xor[u] = xor(root→u)
   • Euler 序号 tin[u], tout[u] → 子树 = 区间 [tin, tout]
     于是 每个查询变成：区间内不同数字的第 k 小。
2. 区间要去重（distinct），又要支持第 k 小，离线比较合适：
   Mo 算法 + Fenwick 树（或 BIT）

详细做法

复杂度

• Mo 移动 O((n+q)·√n) ≈ 2.2e7 操作
• BIT 查询 / k-th O(log U)，U ≤ n
  整体 ~ 2.2e7 × log(5e4) < 4e8 基本 1 s 内能过（Java 也可压线）。
  空间 O(n)。

代码

java
class Solution {
    /* -------- Fenwick / BIT -------- */
    static final class BIT {
        int n; int[] tree;
        BIT(int n){ this.n = n; tree = new int[n+1]; }
        void add(int i,int v){ for(++i;i<=n;i+=i&-i) tree[i]+=v; }
        int sum(int i){ int s=0; for(++i;i>0;i-=i&-i) s+=tree[i]; return s; }
        int total(){ return sum(n-1); }
        // kth (1-indexed): smallest idx s.t. prefix >= k
        int kth(int k){
            int idx=0, bit=highestOneBit(n);
            for(; bit!=0; bit>>=1){
                int next = idx+bit;
                if(next<=n && tree[next]<k){
                    idx=next;
                    k-=tree[next];
                }
            }
            return idx; // 0-indexed
        }
        private static int highestOneBit(int x){ return Integer.highestOneBit(x); }
    }

    /* -------- Mo Query -------- */
    static class Query{
        int l,r,k,id;
        Query(int l,int r,int k,int id){this.l=l;this.r=r;this.k=k;this.id=id;}
    }

    public int[] kthSmallest(int[] par, int[] vals, int[][] queries) {
        int n = vals.length, q = queries.length;

        // 1. build tree adjacency
        List<List<Integer>> g = new ArrayList<>();
        for(int i=0;i<n;i++) g.add(new ArrayList<>());
        for(int i=1;i<n;i++){ g.get(par[i]).add(i); }

        // 2. DFS euler & xor to root
        int[] tin = new int[n], tout = new int[n], euler = new int[n];
        int[] xor = new int[n];
        final int[] time = {0};
        dfs(0,0,g,vals,xor,tin,tout,euler,time);

        // 3. 离散化 xor 值
        int[] arr = new int[n];
        for(int i=0;i<n;i++) arr[i] = xor[i];
        int[] ord = Arrays.copyOf(arr,n);
        Arrays.sort(ord);
        ord = Arrays.stream(ord).distinct().toArray();
        int U = ord.length;
        int[] comp = new int[n];
        for(int i=0;i<n;i++) comp[i] = Arrays.binarySearch(ord, xor[euler[i]]);

        // 4. 转换 queries -> 区间 & 离线
        Query[] qs = new Query[q];
        for(int i=0;i<q;i++){
            int u = queries[i][0], k = queries[i][1];
            qs[i] = new Query(tin[u], tout[u], k, i);
        }
        int B = (int)Math.sqrt(n);
        Arrays.sort(qs, (a,b) -> {
            int ablock = a.l / B, bblock = b.l / B;
            if(ablock!=bblock) return ablock - bblock;
            return (ablock&1)==0 ? a.r - b.r : b.r - a.r;
        });

        // 5. Mo 主循环
        int[] freq = new int[U];
        BIT bit = new BIT(U);
        int curL = 0, curR = -1;
        int[] ans = new int[q];

        for(Query qu : qs){
            while(curL > qu.l) add(--curL, comp, freq, bit);
            while(curR < qu.r) add(++curR, comp, freq, bit);
            while(curL < qu.l) remove(curL++, comp, freq, bit);
            while(curR > qu.r) remove(curR--, comp, freq, bit);

            int distinct = bit.total();
            if(distinct < qu.k) ans[qu.id] = -1;
            else {
                int idx = bit.kth(qu.k);      // idx 是离散后下标
                ans[qu.id] = ord[idx];        // 转回原值
            }
        }
        return ans;
    }

    private static void add(int pos,int[] comp,int[] freq,BIT bit){
        int v = comp[pos];
        if(++freq[v]==1) bit.add(v,1);
    }
    private static void remove(int pos,int[] comp,int[] freq,BIT bit){
        int v = comp[pos];
        if(--freq[v]==0) bit.add(v,-1);
    }

    /* DFS, 记录 euler */
    private static void dfs(int u,int xr,List<List<Integer>> g,int[] vals,
                            int[] xor,int[] tin,int[] tout,int[] euler,int[] time){
        xor[u] = xr ^ vals[u];
        tin[u] = time[0];
        euler[ time[0] ] = u;
        time[0]++;
        for(int v: g.get(u))
            dfs(v, xor[u], g, vals, xor, tin, tout, euler, time);
        tout[u] = time[0]-1;
    }
}

小结

• 问题 1：统计每条水平/垂直可当底边的最大跨距，再配全局最远高。
• 问题 2：滑动窗口 + 两个单调队列维护质数差，双端队列数质数位置即可 O(n).
• 问题 3：树转区间 + Mo 算法 + BIT，在 5 万数据量内完全可过。

如需进一步解释或调优，欢迎继续交流!