2022-03-07：K 个关闭的灯泡。 N 个灯泡排成一行，编号从

原创

福大大架构师每日一题

修改于 2022-03-10 09:57:32

4930

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2022-03-07：K 个关闭的灯泡。

N 个灯泡排成一行，编号从 1 到 N 。最初，所有灯泡都关闭。每天只打开一个灯泡，直到 N 天后所有灯泡都打开。

给你一个长度为 N 的灯泡数组 blubs ，其中 bullsi = x 意味着在第 (i+1) 天，我们会把在位置 x 的灯泡打开，其中 i 从 0 开始，x 从 1 开始。

给你一个整数 K ，请你输出在第几天恰好有两个打开的灯泡，使得它们中间正好有 K 个灯泡且这些灯泡全部是关闭的。

如果不存在这种情况，返回 -1 。如果有多天都出现这种情况，请返回最小的天数。

力扣683。

答案2022-03-07：

时间紧，具体见代码。

代码用golang编写。代码如下：

package main

import (
	"fmt"
	"math"
)

func main() {
	arr := []int{1, 3, 2}
	k := 1
	ret := kEmptySlots2(arr, k)
	fmt.Println(ret)
}

func kEmptySlots2(bulbs []int, k int) int {
	n := len(bulbs)
	days := make([]int, n)
	for i := 0; i < n; i++ {
		days[bulbs[i]-1] = i + 1
	}
	ans := math.MaxInt64
	for left, mid, right := 0, 1, k+1; right < n; mid++ {
		// 验证指针mid
		// mid 永远不和left撞上的！
		// 1) mid在left和right中间验证的时候，没通过！
		// 2) mid是撞上right的时候
		if days[mid] <= getMax(days[left], days[right]) {
			if mid == right { // 收答案！
				ans = getMin(ans, getMax(days[left], days[right]))
			}
			left = mid
			right = mid + k + 1
		}
	}
	if ans == math.MaxInt64 {
		return -1
	} else {
		return ans
	}
}

func getMax(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func getMin(a, b int) int {
	if a < b {
		return a
	} else {
		return b
	}
}

执行结果如下：