菜单 学习猿地 - LMONKEY

VIP

开通学习猿地VIP

尊享10项VIP特权 持续新增

知识通关挑战

打卡带练!告别无效练习

接私单赚外块

VIP优先接,累计金额超百万

学习猿地私房课免费学

大厂实战课仅对VIP开放

你的一对一导师

每月可免费咨询大牛30次

领取更多软件工程师实用特权

入驻
388
0

滑动窗口模板

原创
05/13 14:22
阅读数 31930

滑动窗口模板

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;
    }
}

参考

多看几个题解:

  1. lc 的官方题解: 爱生气的书店老板
    一般官方题解的思路会非常详细,建议多看几遍
  2. 用「秘密技巧」挽留住最多的原本因为生气而被赶走的顾客

发表评论

0/200
388 点赞
0 评论
收藏
为你推荐 换一批