嗨客网搜索
爱生气的书店老板

描述

力扣第 1052 题。今天,书店老板有一家店打算试营业 customers.length 分钟。每分钟都有一些顾客(customers[i])会进入书店,所有这些顾客都会在那一分钟结束后离开。

在某些时候,书店老板会生气。 如果书店老板在第 i 分钟生气,那么 grumpy[i] = 1,否则 grumpy[i] = 0。 当书店老板生气时,那一分钟的顾客就会不满意,不生气则他们是满意的。

书店老板知道一个秘密技巧,能抑制自己的情绪,可以让自己连续 X 分钟不生气,但却只能使用一次。

请你返回这一天营业下来,最多有多少客户能够感到满意的数量。

示例:

输入:customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3 输出:16 解释: 书店老板在最后 3 分钟保持冷静。 感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.

提示

  • 1 <= X <= customers.length == grumpy.length <= 20000
  • 0 <= customers[i] <= 1000
  • 0 <= grumpy[i] <= 1

思路

这是一个情景题,换个表述就是查询 customers 数组中对应的数组下标与 grumpy 的值是 0 的数组下标的值之和。并且给出了一个数值 X,要求该范围长度内的 customers 数组中,值是 1 的换成 0,获取到最大的值。

我们以上面的示例做一个场景分析:

20_爱生气的书店老板.png

黄色的数据表示的是 grumpy 数组里面对应的数据,它 0 表示没有生气,1 表示生气。我们可以先遍历 customers 数组,将 grumpy 是 0 的位置的数据相加,得到的和为 : 1 + 1 + 1 + 7 = 10。

题目中,书店的老板可以控制 3 分钟。我们可以看作是一个滑动窗口,一步一步的往后移动,具体步骤如下:

  • 第一步:我们可以将三分钟控制在开始的地方,那么前三分钟,老板是不会生气的,所以,我们可以认为 customers 数组的第 0 个位置到第 2 个位置,都是 0。而第二个位置原先是 1,所以我们需要再加上第二个位置的客流量:0。
  • 第二步:我们将三分钟的时间向后移动一个,从 customers 数组的第 1 个位置到第 3 个位置。所以这个时候老板的第一个位置和第三个位置的客人是没有被生气到的,则在原先的基础上再加 0 + 2 = 2。
  • 第三步:我们将三分钟的时间向后移动一个,从 customers 数组的第 2 个位置到第 4 个位置。所以这个时候老板的第三个位置的客人是没有被生气到的,则在原先的基础上再加 2。
  • 第四步:我们将三分钟的时间向后移动一个,从 customers 数组的第 3 个位置到第 5 个位置。所以这个时候老板的第三个位置和第五个位置的客人是没有被生气到的,则在原先的基础上再加 2 + 1 = 3。
  • 第五步:我们将三分钟的时间向后移动一个,从 customers 数组的第 4 个位置到第 6 个位置。所以这个时候老板的第五个位置的客人是没有被生气到的,则在原先的基础上再加 1。
  • 第五步:我们将三分钟的时间向后移动一个,从 customers 数组的第 5 个位置到第 7 个位置。所以这个时候老板的第五个位置和第七个位置的客人是没有被生气到的,则在原先的基础上再加 1 + 5 = 6。

所以综上,我们需要获取到被修改的数据的最大值 6,再与 10 相加,就得到最终的 16。

代码具体实现

Java语言

class Solution { public int maxSatisfied(int[] customers, int[] grumpy, int X) { int total = 0; //如果冷静期比当前数组长度大,则可以将所有数据直接相加 if (X > customers.length) { for (int i = 0; i < customers.length; i++) { if (grumpy[i] == 0) { total = total + customers[i]; } } return total; } //获取所有冷静期的所有数据 for (int i = 0; i < customers.length; i++) { if (grumpy[i] == 0) { total = total + customers[i]; } } //根据滑动窗口,将冷静期里面数值为 1 的数据获取,取最大值 int increase = 0; for (int i = 0; i <= customers.length - X; i++) { int tmpIncrease = 0; for (int j = 0; j < X; j++) { if (grumpy[i + j] == 1) { tmpIncrease = tmpIncrease + customers[j + i]; } } if (tmpIncrease > increase) { increase = tmpIncrease; } } return total + increase; } }

Go语言

func maxSatisfied(customers []int, grumpy []int, X int) int { total := 0 //如果冷静期比当前数组长度大,则可以将所有数据直接相加 if X > len(customers) { for i := 0; i < len(customers); i++ { if grumpy[i] == 0 { total = total + customers[i] } } return total } //获取所有冷静期的所有数据 for i := 0; i < len(customers); i++ { if grumpy[i] == 0 { total = total + customers[i] } } //根据滑动窗口,将冷静期里面数值为 1 的数据获取,取最大值 increase := 0 for i := 0; i <= len(customers) - X; i++ { tmpIncrease := 0 for j := 0; j < X; j++ { if grumpy[i + j] == 1 { tmpIncrease = tmpIncrease + customers[j + i] } } if tmpIncrease > increase { increase = tmpIncrease } } return total + increase }
嗨客网顶部