LEETCODE 1052. Grumpy Bookstore Owner 解题思路分析

题目大意:

爱生气的书店老板

今天,书店老板有一家店打算试营业 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


如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1052

解题思路分析:

题目要求求出最多有多少客户能够感到满意的数量,也就是在老板不生气的时间点内来店的客户数量总和。而生气时间点的客户数量不会记在结果之内。另外老板有个技能,能在x分钟内连续不生气,这是本题的关键,老板开技能的时间点至关重要,如果在这个时间段内,能够将更多的不满意变为满意,即为最优解。因此题目就转化为找到连续x区间内,不满意客户的最大数量。具体实现参照代码注释。

看下完整代码:

public int maxSatisfied(int[] customers, int[] grumpy, int X) {
    // 前缀和数组,lostUser[i]表示区间[0, i]之间不满意人数和。
    int[] lostUser = new int[customers.length];
    // max为X区间内最多不满意人数,maxIndex为区间终点
    int max=0, maxIndex=0;
    for(int i=0;i<grumpy.length;i++){
        // 计算区间[0, i]之间不满意人数和(前缀和)
        lostUser[i] = (i==0 ? 0 : lostUser[i-1])+(grumpy[i]==0?0:customers[i]);
        // 通过前缀和计算出以i为终点的X长度区间范围内的不满意人数和
        if(lostUser[i] - (i<X ? 0 : lostUser[i-X]) > max){
            // 更新不满意人数最大值
            max = lostUser[i] - (i<X ? 0 : lostUser[i-X]);
            // 更新X区间终点下标
            maxIndex=i;
        }
    }
    int res=0; // 定义返回值。满意人数和
    for(int i=0;i<grumpy.length;i++){
        // 如果老板不生气或者当前为老板开技能区间
        if(grumpy[i]==0 || i>maxIndex-X && i<=maxIndex){
            res+=customers[i]; // 更新人数
        }
    }
    return res;
}

本题解法运行时间为3ms。

Runtime: 3 ms, faster than 85.20% of Java online submissions for Grumpy Bookstore Owner.

Memory Usage: 42.2 MB, less than 100.00% of Java online submissions for Grumpy Bookstore Owner.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-1052-grumpy-bookstore-owner-解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。