L 683. K Empty Slots ---H !!!!!!~~~学习后两种解法

You have N bulbs in a row numbered from 1 to N. Initially, all the bulbs are turned off. We turn on exactly one bulb everyday until all bulbs are on after N days.

You are given an array bulbs of length N where bulbs[i] = x means that on the (i+1)th day, we will turn on the bulb at position x where i is 0-indexed and x is 1-indexed.

Given an integer K, find out the minimum day number such that there exists two turned on bulbs that have exactly K bulbs between them that are all turned off.

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

 

Example 1:

Input: 
bulbs: [1,3,2]
K: 1
Output: 2
Explanation:
On the first day: bulbs[0] = 1, first bulb is turned on: [1,0,0]
On the second day: bulbs[1] = 3, third bulb is turned on: [1,0,1]
On the third day: bulbs[2] = 2, second bulb is turned on: [1,1,1]
We return 2 because on the second day, there were two on bulbs with one off bulb between them.

Example 2:

Input: 
bulbs: [1,2,3]
K: 1
Output: -1

 

Note:

1. 1 <= N <= 20000
2. 1 <= bulbs[i] <= N
3. bulbs is a permutation of numbers from 1 to N.
4. 0 <= K <= 20000

A:

就是一个个存进 已经打开的 bulb的位置，然后再检查即可。

这里，我尝试用了 sorted set.

class Solution {
 public:
     int kEmptySlots(vector<int>& bulbs, int K) {
         set<int> S;// save number lights that have been on
         for (int d = 0; d < bulbs.size(); d++) {
             //insert() return a pair, with its member pair::first set to an iterator pointing to either the newly inserted element or to the equivalent element already in the set. 
             //The pair::second element in the pair is set to true if a new element was inserted or false if an equivalent element already existed.
             auto it = S.insert(bulbs[d]).first;
             if (it != S.begin()) {
                 auto pre = --it; // iterator support ++/--, but not -1,+1
                 ++it;// put it back
                 if (*it - *pre - 1 == K) {// -1 because need bulb between them
                     return d+1;
                 }
             }
             auto last = S.end();
             --last;
             if (it != last) { // iterator and reverse iterator are diffrent
                 auto next = ++it;
                 --it;
                 if (*next - *it -1 == K) {
                     return d+1;
                 }
             }
         }
         return -1;
     }
 };

Learned：

S.insert() 返回的是一个pair。 pair.first 是iterator, pair.second是bool( insertedNewElement, or old_already_exist value)

Approach #2: Min Queue [Accepted]

Intuition

For each contiguous block ("window") of k positions in the flower bed, we know it satisfies the condition in the problem statement if the minimum blooming date of this window is larger than the blooming date of the left and right neighbors.

Because these windows overlap, we can calculate these minimum queries more efficiently using a sliding window structure.

Algorithm

Let days[x] = i be the time that the flower at position x blooms. For each window of k days, let's query the minimum of this window in (amortized) constant time using a MinQueue, a data structure built just for this task. If this minimum is larger than it's two neighbors, then we know this is a place where "k empty slots" occurs, and we record this candidate answer.

To operate a MinQueue, the key invariant is that mins will be an increasing list of candidate answers to the query MinQueue.min.

For example, if our queue is [1, 3, 6, 2, 4, 8], then mins will be [1, 2, 4, 8]. As we MinQueue.popleft, mins will become [2, 4, 8], then after 3 more popleft's will become [4, 8], then after 1 more popleft will become [8].

As we MinQueue.append, we should maintain this invariant. We do it by popping any elements larger than the one we are inserting. For example, if we appended 5 to [1, 3, 6, 2, 4, 8], then mins which was [1, 2, 4, 8] becomes [1, 2, 4, 5].

Note that we used a simpler variant of MinQueue that requires every inserted element to be unique to ensure correctness. Also, the operations are amortized constant time because every element will be inserted and removed exactly once from each queue.

Complexity Analysis

• Time Complexity: $O(N)$, where $N$ is the length of flowers. In enumerating through the $O(N)$ outer loop, we do constant work as MinQueue.popleft and MinQueue.min operations are (amortized) constant time.

• Space Complexity: $O(N)$, the size of our window.

---

Approach #3: Sliding Window [Accepted]

Intuition

As in Approach #2, we have days[x] = i for the time that the flower at position x blooms. We wanted to find candidate intervals [left, right] where days[left], days[right] are the two smallest values in [days[left], days[left+1], ..., days[right]], and right - left = k + 1.

Notice that these candidate intervals cannot intersect: for example, if the candidate intervals are [left1, right1] and [left2, right2] with left1 < left2 < right1 < right2, then for the first interval to be a candidate, days[left2] > days[right1]; and for the second interval to be a candidate, days[right1] > days[left2], a contradiction.

That means whenever whether some interval can be a candidate and it fails first at i, indices j < i can't be the start of a candidate interval. This motivates a sliding window approach.

Algorithm

As in Approach #2, we construct days.

Then, for each interval [left, right] (starting with the first available one), we'll check whether it is a candidate: whether days[i] > days[left] and days[i] > days[right] for left < i < right.

If we fail, then we've found some new minimum days[i] and we should check the new interval [i, i+k+1]. If we succeed, then it's a candidate answer, and we'll check the new interval [right, right+k+1].

Complexity Analysis

• Time and Space Complexity: $O(N)$. The analysis is the same as in Approach #2.