写点什么

【LeetCode】爱生气的书店老板 Java 题解

用户头像
HQ数字卡
关注
发布于: 2021 年 02 月 23 日

题目

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


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


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


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


代码

public class DayCode {    public static void main(String[] args) {        int[] customers = new int[]{1,0,1,2,1,1,7,5};        int[] grumpy = new int[]{0,1,0,1,0,1,0,1};        int X = 3;        int ans = new DayCode().maxSatisfied(customers, grumpy, X);        System.out.println("ans is " + ans);    }
/** * https://leetcode-cn.com/problems/grumpy-bookstore-owner/ * 时间复杂度O(n) * 空间复杂度O(1) * @param customers * @param grumpy * @param X * @return */ public int maxSatisfied(int[] customers, int[] grumpy, int X) { int ans = 0; int n = customers.length; int sum = 0; for (int i = 0; i < n; i++) { if (grumpy[i] == 0) { sum += customers[i]; } } int increase = 0; for (int j = 0; j < X; j++) { increase += customers[j] * grumpy[j]; } int maxIncrease = increase; for (int k = X; k < n; k++) { increase = increase - customers[k - X] * grumpy[k - X] + customers[k] * grumpy[k]; maxIncrease = Math.max(increase, maxIncrease); } ans = sum + maxIncrease; return ans; }}
复制代码

总结

  • 题目描述比较长,但是容易理解。

  • 首先求出不生气情况下的客户数,在使用滑动窗口求出最大的满意客户数,相加就是结果。

  • 每日坚持一题,加油!


发布于: 2021 年 02 月 23 日阅读数: 7
用户头像

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】爱生气的书店老板Java题解