lcp365

100088. 有序三元组中的最大值 I

方法一：暴力

class Solution {
    public long maximumTripletValue(int[] nums) {
        long n = nums.length, 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, (long) (nums[i] - nums[j]) * nums[k]);
                }
            }
        }
        return Math.max(res, 0);
    }
}

100086. 有序三元组中的最大值 II

方法一：滑动窗口

class Solution {
    public long maximumTripletValue(int[] nums) {
        int n = nums.length, l = 0;
        long res = 0, diff = 0, preMax = Integer.MIN_VALUE, maxK = 0;
        for (int i = 1; i < n - 1; ++i) {
            diff = nums[l] - nums[i];
            if (nums[l] < nums[i])
                l = i;
            if (preMax < diff) 
                preMax = diff;
            res = Math.max(res, preMax * nums[i + 1]);
        }
        return Math.max(res, 0);
    }
}

方法二：维护左右最大值

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

100076. 无限数组的最短子数组

方法二：滑动窗口

class Solution {
    public int minSizeSubarray(int[] nums, int target) {
        int n = nums.length, res = Integer.MAX_VALUE / 2, sum = 0;
        long s = 0;
        for (int x : nums)
            sum += x;
        int cnt = target / sum;
        target = target % sum;
        int l = 0;
        for (int i = 0; i < 2 * n; ++i) {
            s += nums[i % n];
            while (s > target) {
                s -= nums[l % n];
                ++l;
            }
            if (s == target)
                res = Math.min(res, i - l + 1);
        }
        return res == Integer.MAX_VALUE / 2 ? -1 : res + cnt * n;
    }
}

方法一：前缀和 + HashMap

class Solution {
    public int minSizeSubarray(int[] nums, int t) {
        int n = nums.length;
        long res = Integer.MAX_VALUE / 2;
        Map<Long, Integer> map = new HashMap<>();
        int[] arr = new int[3 * n];
        long sum = 0, target = t;
        for (int i = 0; i < 3 * n; ++i) {
            arr[i] = nums[i % n];
            if (i < n)
                sum += nums[i];
        }
        boolean flag = false;
        long extra = 0;
        if (target >= 2 * sum) {
            extra = target / sum * n;
            target %= sum;
            flag = true;
        }
        sum = 0;
        boolean find = false;
        for (int i = 0; i < 3 * n; ++i) {
            sum += arr[i];
            map.put(sum, i);
            if (map.containsKey(sum - target)) {
                find = true;
                res = Math.min(res, i - map.get(sum - target));
            }
        }
        if (flag)
            res += extra;
        return !find ? -1 : (int) res;
    }
}

2876. 有向图访问计数

方法一：拓扑排序 + 反向图

注意内向基环图可以包含多个环！！！

class Solution {
    public int[] countVisitedNodes(List<Integer> g) {
        int n = g.size();
        int[] degree = new int[n];
        List<Integer>[] rg = new List[n];
        Arrays.setAll(rg, e -> new ArrayList<>());
        for (int i = 0; i < n; ++i) {
            int from = i, to = g.get(i);
            degree[to]++;
            rg[to].add(from);
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; ++i)
            if (degree[i] == 0)
                queue.offer(i);
        while (!queue.isEmpty()) {
            int node = queue.poll();
            int next = g.get(node);
            if (--degree[next] == 0)
                queue.offer(next);
        }
        int[] res = new int[n];
        for (int i = 0; i < n; ++i) {
            if (degree[i] <= 0)
                continue;
            List<Integer> ring = new ArrayList<>();
            int j = i;
            while (true) {
                ring.add(j);
                degree[j] = -1;
                j = g.get(j);
                if (j == i)
                    break;
            }
            for (int x : ring)
                dfs(x, ring.size(), rg, res, degree);
        }
        return res;
    }

    private void dfs(int x, int size, List<Integer>[] rg, int[] res, int[] degree) {
        res[x] = size;
        for (int next : rg[x]) {
            if (degree[next] == 0)
                dfs(next, size + 1, rg, res, degree);
        }
    }

}