当前位置 博文首页 > 数据结构和算法：LeetCode 1052. 爱生气的书店老板
截止到目前我已经写了 500多道算法题，其中部分已经整理成了pdf文档，目前总共有1000多页（并且还会不断的增加），大家可以免费下载
下载链接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码：6666
来看下代码
public int maxSatisfied(int[] customers, int[] grumpy, int X) {
int satisfied = 0;//先统计本来就满意的
int length = grumpy.length;
//新的数组，统计不满意的
int[] noSatisfied = new int[length];
for (int i = 0; i < length; i++) {
if (grumpy[i] == 0)
satisfied += customers[i];
else
noSatisfied[i] = customers[i] * grumpy[i];
}
//使用两个指针，类似于窗口的左边和右边
int left = 0;
int right = 0;
int max = 0;//记录窗口内的最大值
int sum = 0;//记录当前窗口内的值
for (; right < length; right++) {
sum += noSatisfied[right];
//如果窗口长度超过K，要减去窗口左边的值，同时
//窗口左边要往右移一步
if (right - left >= X) {
sum -= noSatisfied[left++];
}
//保存最大值
max = Math.max(max, sum);
}
//本来就满意的+老板控制情绪让顾客满意的
return satisfied + max;
}
上面计算的时候我们使用了两个for循环，实际上我们还可以把他们合并成一个
public int maxSatisfied(int[] customers, int[] grumpy, int X) {
int satisfied = 0;//本来就满意的
int maxPretendSatisfied = 0;//最大抑制情绪满意的
int pretendSatisfied = 0;//窗口内抑制情绪满意的
for (int i = 0; i < grumpy.length; ++i) {
//如果grumpy[i]是0，表示顾客是满意的
if (grumpy[i] == 0) {
satisfied += customers[i];
} else {
//如果不等于0，表示顾客是不满意的，但老板可以控制自己的
//情绪，顾客表示假装满意
pretendSatisfied += customers[i];
}
//老板控制自己的情绪是有限的，这个范围我们可以把它看做是一个窗口，
//这个窗口是一直往右移动的，如果移除窗口的有不满意的，要减去
if (i >= X && grumpy[i - X] == 1) {
pretendSatisfied -= customers[i - X];
}
//保存通过抑制情绪使顾客满意的最大数量
maxPretendSatisfied = Math.max(maxPretendSatisfied, pretendSatisfied);
}
//最后返回本来就使顾客满意的数量+抑制情绪使顾客满意的数量
return satisfied + maxPretendSatisfied;
}
