第 365 场力扣周赛

有序三元组中的最大值 I

同下。

有序三元组中的最大值 II

方法一：枚举 j

比赛时第一想法是枚举 \(j\)，然后取左边和右边的最大值计算答案。

class Solution {
    public long maximumTripletValue(int[] nums) {
        int n = nums.length;
        int[] pre = new int[n + 1];
        int[] suf = new int[n + 1];
        for (int i = 0; i < n; i++) {
            pre[i + 1] = Math.max(pre[i], nums[i]);
        }
        for (int i = n - 1; i >= 0; i--) {
            suf[i] = Math.max(suf[i + 1], nums[i]);
        }
        long ans = 0L;
        for (int j = 1; j < n - 1; j++) {
            ans = Math.max(ans, (long) (pre[j] - nums[j]) * suf[j + 1]);
        }
        return ans;
    }
}

方法二：枚举 k

参考灵神的题解，可以枚举 \(k\)，使空间复杂度降为 \(O(1)\)。主要想法就是枚举时，维护前缀最大差值。

class Solution {
    public long maximumTripletValue(int[] nums) {
        long ans = 0;
        int maxDiff = 0, preMax = 0;
        for (int x : nums) {
            ans = Math.max(ans, (long) maxDiff * x);
            maxDiff = Math.max(maxDiff, preMax - x);
            preMax = Math.max(preMax, x);
        }
        return ans;
    }
}

无限数组的最短子数组

比赛时思路很快出来，但是实现的时候漏掉一些边界条件，导致 WA 多次，本来有机会进第一页的。比较直接的想法是枚举起始位置，然后利用前缀和二分结束的位置，如果满足条件就记入答案。也可以使用哈希表来优化，避免二分。这里贴一下灵神的滑动窗口解法，时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。

class Solution {
    public int minSizeSubarray(int[] nums, int target) {
        int n = nums.length;
        long sum = 0L, pre = 0L;
        for (int x : nums) sum += x;
        int q = (int) (target / sum), r = (int) (target % sum);
        int lo = 0, hi = 0, ans = Integer.MAX_VALUE;
        while (hi < 2 * n) {
            pre += nums[hi++ % n];
            while (pre > r) {
                pre -= nums[lo++ % n];
            }
            if (pre == r) {
                ans = Math.min(ans, hi - lo);
            }
        }
        return ans == Integer.MAX_VALUE ? -1 : ans + q * n;
    }
}

有向图访问计数

看完题目就知道是内向基环树，直接修改上次的代码，轻松通过，本题是上次的简化版。

class Solution {
    public int[] countVisitedNodes(List<Integer> edges) {
        int n = edges.size();
        // 建立环外节点的反向边
        int[] in = new int[n];
        List<Integer>[] reverse = new List[n];
        Arrays.setAll(reverse, r -> new ArrayList<>());
        for (int i = 0; i < n; i++) {
            in[edges.get(i)]++;
            reverse[edges.get(i)].add(i);
        }
        // 拓扑序去除环外节点
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (in[i] == 0) q.add(i);
        }
        while (!q.isEmpty()) {
            int x = q.poll();
            if (--in[edges.get(x)] == 0) {
                q.offer(edges.get(x));
            }
        }
        // 记录每个节点在哪个环
        int[] cirNum = new int[n];
        boolean[] vis = new boolean[n];
        List<Integer> circles = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (!vis[i] && in[i] != 0) {
                int cnt = 0;
                for (int cur = i; !vis[cur]; cur = edges.get(cur)) {
                    vis[cur] = true;
                    cirNum[cur] = circles.size();
                    cnt++;
                }
                circles.add(cnt);
            }
        }
        // 对环内的每个节点向环外进行 dfs
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            if (in[i] != 0) dfs(i, reverse, in, circles.get(cirNum[i]), ans);
        }
        return ans;
    }
    
    private void dfs(int x, List<Integer>[] reverse, int[] in, int len, int[] ans) {
        ans[x] = len;
        for (int y : reverse[x]) {
            if (in[y] != 0) continue;
            dfs(y, reverse, in, len + 1, ans);
        }
    }
}

有个非常简单的写法，参考题解。

class Solution {
    public int[] countVisitedNodes(List<Integer> edges) {
        int n = edges.size();
        int[] ans = new int[n];
        int[] vis = new int[n];
        for (int i = 0; i < n; i++) {
            if (ans[i] == 0) {
                int cnt = 0, cirLen = 0, totLen = 0, pos = i;
                while (vis[pos] == 0) {
                    vis[pos] = ++cnt;
                    pos = edges.get(pos);
                }
                if (ans[pos] == 0) {
                    cirLen = cnt - vis[pos] + 1;
                    totLen = cnt;
                } else {
                    totLen = cnt + ans[pos];
                }
                pos = i;
                while (ans[pos] == 0) {
                    ans[pos] = Math.max(totLen--, cirLen);
                    pos = edges.get(pos);
                }
            }
        }
        return ans;
    }
}