滑动窗口模板
以 1052. 爱生气的书店老板 为例
class Solution {
/**
* @param Integer[] $customers
* @param Integer[] $grumpy
* @param Integer $X
* @return Integer
*/
function maxSatisfied($customers, $grumpy, $X) {
if (empty($customers)) {
return 0;
}
// 1. 计算初始状态: 不压抑的时候,最大的满意人数
$maxSat = 0;
foreach ($grumpy as $key => $g) {
if ($g == 0) {
$maxSat += $customers[$key];
}
}
// 1.1 初始化左右指针位置
$len = count($customers);
$left = $right = 0;
$curSat = $maxSat;
// 2. 滑窗具体代码
// 2.1 右指针一直往右做
while ($right < $len) {
$span = $right - $left + 1;
// 2.1 直到遇到临界条件之后,左指针往右走,知道满足临界条件
if ($span > $X) {
if ($grumpy[$left]) {
$curSat -= $customers[$left];
}
$left ++;
}
// 计算当前窗口的数值
if ($grumpy[$right]) {
$curSat += $customers[$right];
}
// 最终结果比较
$maxSat = max($curSat, $maxSat);
$right++;
}
return $maxSat;
}
}
参考
多看几个题解:
- lc 的官方题解: 爱生气的书店老板
一般官方题解的思路会非常详细,建议多看几遍 - 用「秘密技巧」挽留住最多的原本因为生气而被赶走的顾客