[Leetcode Weekly Contest]365

链接：LeetCode

[Leetcode]2873. 有序三元组中的最大值 I

给你一个下标从 0 开始的整数数组 nums 。
请你从所有满足 i < j < k 的下标三元组 (i, j, k) 中，找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数，则返回 0 。
下标三元组 (i, j, k) 的值等于 (nums[i] - nums[j]) * nums[k] 。

暴力即可，\(O(N^3)\)

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

[Leetcode]2874. 有序三元组中的最大值 II

给你一个下标从 0 开始的整数数组 nums 。
请你从所有满足 i < j < k 的下标三元组 (i, j, k) 中，找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数，则返回 0 。
下标三元组 (i, j, k) 的值等于 (nums[i] - nums[j]) * nums[k] 。

贪心。
首先，输出的数值最小为 0，同时数组中每个元素均为正数，因此，我们要让 (nums[i] - nums[j]) * nums[k] 最大，只需要对于固定的 k 找到其前面 nums[i] - nums[j] 的最大值。
为了使得 nums[i] - nums[j] 尽可能大，我们需要对于固定的 j 找到其前面最大的 nums[i] 再将两者相减。因此我们只需要维护三个东西：到当前位置的最大值，到当前位置为止最大的 nums[i] - nums[j]，到当前位置为止最大的 (nums[i] - nums[j]) * nums[k]. 而从上面的分析可以看出，这些都可以遍历过程中实现。
因此时间复杂度是\(\mathcal{O}(n)\) 的。

class Solution {
    public long maximumTripletValue(int[] nums) {
        Deque<Integer> stack = new ArrayDeque<>();
        long res = 0, maxDiff = 0;
        long max = nums[0], min = nums[0];
        for(int i=0;i<nums.length-1;++i) {
            if(nums[i] > max) {
                max = nums[i];
                min = nums[i];
            } else if(nums[i] < min) {
                min = nums[i];
            }
            maxDiff = Math.max(maxDiff, max-min);
            res = Math.max(res, maxDiff * nums[i+1]);
        }
        return res;
    }
}

[Leetcode]2875. 无限数组的最短子数组

给你一个下标从 0 开始的数组 nums 和一个整数 target 。
下标从 0 开始的数组 infinite_nums 是通过无限地将 nums 的元素追加到自己之后生成的。
请你从 infinite_nums 中找出满足 元素和 等于 target 的 最短 子数组，并返回该子数组的长度。如果不存在满足条件的子数组，返回 -1 。

因为是无限循环的，所以结果可能是 任意 k 个完整的数组加上循环数组中的一部分。
提前求出有几个完整的，然后用滑动窗口计算最小的窗口。

class Solution {
    public int minSizeSubarray(int[] nums, int target) {
        int sum = getSum(nums);
        int n = nums.length;
        int[] doubleNums = new int[2*n];
        for(int i=0;i<n;++i) doubleNums[i] = nums[i];
        for(int i=n;i<2*n;++i) doubleNums[i] = nums[i-n];
        int res = getMinSizeSubarray(doubleNums, target % sum);
        return res == Integer.MAX_VALUE ? -1 : res + target / sum * n;
    }

    private int getMinSizeSubarray(int[] nums, int target) {
        if(target == 0) return 0;
        int res = Integer.MAX_VALUE;
        int start = 0;
        int sum = 0;
        for(int i=0;i<nums.length;++i) {
            sum += nums[i];
            while(sum > target) {
                sum -= nums[start];
                start ++;
            }
            if(sum == target) res = Math.min(res, i-start+1);
        }
        return res;
    }

    private int getSum(int[] nums) {
        int res = 0;
        for(int num:nums) res += num;
        return res;
    }
}

[Leetcode]2876. 有向图访问计数

现有一个有向图，其中包含 n 个节点，节点编号从 0 到 n - 1 。此外，该图还包含了 n 条有向边。
给你一个下标从 0 开始的数组 edges ，其中 edges[i] 表示存在一条从节点 i 到节点 edges[i] 的边。
想象在图上发生以下过程：

• 你从节点 x 开始，通过边访问其他节点，直到你在 此过程 中再次访问到之前已经访问过的节点。

返回数组 answer 作为答案，其中 answer[i] 表示如果从节点 i 开始执行该过程，你可以访问到的不同节点数。

这是一个经典的类型的图——基环树，每个点都只有一条出去的边。其有特点：所有的点要么在环上，要么有一条路径走向环。环上的点不会有往外的边（因为该点的边指向环中其他的点）。
先找到所有的环，环上所有点能到达的点都是环上的点。接下来从环上的点出发往外走，每个点能到达的新的点可以进行访问点数的更新。如果原节点能到达 k 个，则往外走一步的新节点能到达 k+1 个点。

找环我们可以使用拓扑排序来做，即不断找入度为 0 的点放入栈中，删去其出边，再放入新产生的入度为 0 的点，最后剩下的图只有环，最后环里的所有点可以通过 DFS 等方式得到。

时间复杂度为 \(\mathcal{O}(n)\).

class Solution {
    public int[] countVisitedNodes(List<Integer> edges) {
        int n = edges.size();
        List<List<Integer>> rev = new ArrayList<>();
        int[] indegree = new int[n];
        for(int i=0;i<n;++i) {
            rev.add(new ArrayList<>());
        }
        for(int i=0;i<n;++i) {
            int v = edges.get(i);
            indegree[v] += 1;
            rev.get(v).add(i);
        }

        // 拓扑排序
        Deque<Integer> stack = new ArrayDeque<>();
        for(int i=0;i<n;++i) {
            if(indegree[i] == 0) stack.push(i);
        }
        while(!stack.isEmpty()) {
            int u = stack.pop();
            int v = edges.get(u);
            indegree[v] --;
            if (indegree[v] == 0) {
                stack.push(v);
            }
        }

        // 找环里的点
        int[] res = new int[n];
        for(int i=0;i<n;++i) {
            if(indegree[i] > 0) {
                LinkedList<Integer> elements = new LinkedList<>(List.of(i));
                while(edges.get(elements.getLast()) != i) {
                    elements.add(edges.get(elements.getLast()));
                }
                for(int element:elements) {
                    res[element] = elements.size();
                    indegree[element] = 0;
                }
            }
        }

        // 更新环外的点
        for(int i=0;i<n;++i) {
            if(res[i] == 0) continue;
            Deque<Integer> temp = new ArrayDeque<>(List.of(i));
            while(!temp.isEmpty()) {
                int u = temp.pop();
                for(int v: rev.get(u)) {
                    if(res[v] == 0) {
                        res[v] = res[u] + 1;
                        temp.push(v);
                    }
                }
            }
        }
        return res;
    }
}

参考：LeetCode