我如何分析k个空槽算法？

Question

Leet Code 上有一个叫做 K 空槽的算法。我不明白这些限制。我尝试研究对这个问题的更好解释，但我找不到。具体如下：

There is a garden with N slots. In each slot, there is a flower. The N flowers will bloom one by one in N days. In each day, there will be exactly one flower blooming and it will be in the status of blooming since then.

Given an array flowers consists of number from 1 to N. Each number in the array represents the place where the flower will open in that day.

For example, flowers[i] = x means that the unique flower that blooms at day i will be at position x, where i and x will be in the range from 1 to N.

Also given an integer k, you need to output in which day there exists two flowers in the status of blooming, and also the number of flowers between them is k and these flowers are not blooming.

If there isn't such day, output -1.

Example 1:

Input:

flowers: [1,3,2]

k: 1

Output: 2

Explanation: In the second day, the first and the third flower have become blooming.

Example 2:

Input:

flowers: [1,2,3]

k: 1

Output: -1

Note:

The given array will be in the range [1, 20000].

我想自己解决。我想知道是否有更简单的问题解释。我不明白 k 输入。我不明白为什么第一个示例返回 2 而第二个示例返回 -1。

Answer 1

根据问题陈述：

1) 有一个花园有N个槽位。在每个插槽中，有一朵花。 N天后，N朵花将一朵一朵地绽放。每一天，恰好有一朵花开，从那时起就处于盛开状态

它基本上告诉我们有一个大小为 N 的数组，这些数组是每天开一朵花的槽。所以数组大小会告诉你花的数量。

2) 给定一个数组flowers，由1到N的数字组成，数组中的每个数字代表当天花朵开放的位置

arr[i] 会告诉你花开的时间，i (index) 会告诉你那天花开的日期。例如：

[1,3,2] 这里表示

第 1 天：插槽 1 中的花将盛开。
第 2 天：插槽 3 中的花将盛开。
第 3 天：插槽 2 中的花将盛开

3) 同样给定一个整数k，需要输出哪一天有两朵花处于开花状态，并且它们之间的花数为k而且这些花没有开。

从这个语句中，我们了解到我们必须 输出那一天 当两朵盛开的花在那些槽中时，它们之间的槽应该是空的，并且数字它们之间的槽数等于 k。如果没有这样的插槽，return -1.

对于第一个例子。 [1,3,2] 如上所述，第 2 天花将在槽 3 上盛开，而在第 1 天花将在槽 1 上盛开，因此第 2 天空闲的槽数为 1（等于 k）它们之间。因此输出是第 2 天。

对于第二个例子，我们看到花在连续的槽中，所以它们之间没有未开花的花槽，因此输出是-1。

希望对您有所帮助！

Answer 2

你需要找到一个子数组，在2朵开花的花之间有k朵未开花的花。

public int kEmptySlots(int[] flowers, int k) {
        int[] days = new int[flowers.length];
        for (int i = 0; i < days.length; i++) {
            days[flowers[i] - 1] = i + 1;
        }
        int left = 0;
        int right = k + 1;
        int res = Integer.MAX_VALUE;
        for (int i = 1; right < days.length; i++) {
            // current days[i] is valid, continue scanning
            if (days[i] > days[left] && days[i] > days[right]) {
                continue;
            }
           // reach boundary of sliding window, since previous number are all valid, record result  
            if (i == right) {
                res = Math.min(res, Math.max(days[left],days[right]));
            }
            // not valid, move the sliding window
            left = i;
            right = left + k + 1;
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }

Answer 3

最优解可以是：

class Solution {
public int kEmptySlots(int[] flowers, int k) {
    TreeSet<Integer> active = new TreeSet();
    int day = 0;
    for (int flower: flowers) {
        day++;
        active.add(flower);
        Integer lower = active.lower(flower)
        Integer higher = active.higher(flower);
        if (lower != null && flower - lower - 1 == k ||
                higher != null && higher - flower - 1 == k)
            return day;
    }
    return -1;
}

}

我如何分析k个空槽算法？

How do I analyze k empty slots algorithm?

algorithm

data-structures

array-algorithms