You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

1052. 爱生气的书店老板 - Grumpy Bookstore Owner

. 3 min read

【动态规划】

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

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

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

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

Example:

示例:

输入: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

Analysis

定义:

v[i]:在时刻 i 时满意的客人数量, 则

$$\begin{equation}
v[i]=\left{
​             \begin{array}{lr}
​             \text{0,}&\quad\text{如果书店老板生气:grumpy[i] = 1,}\
​             \text{customers[i],} &\quad\text{如果书店老板不生气:grumpy[i] = 0.}
​             \end{array}
\right.
\end{equation} $$

即:$v[i] = customers[i] & (grumpy[i] - 1)$

这里使用位操作计算,也可以基于判断操作

x[i]: 在时间 $[0, i]$ 内,未使用防止暴脾气时的最大满意值 ,则

$$\begin{equation}
x[i]=x[i-1] + v[i]
\end{equation} $$

y[i]: 在时间 $[0, i]$ 内,使用防止暴脾气后的最大满意值。则

$$\begin{equation}
y[i]=max\left{
\begin{array}{lr}
v[i]+y[i-1]&\quad\text{时刻 i 技能已经结束,}\
\sum\limits_{k=i-X+1}^{i}(customers[k]) + x[i-X]&\quad\text{时刻 i 技能未结束,按恰好结束计算即取最大.}
\end{array}
\right.
\end{equation}$$

最终结果为:$y[i]=max{x[end_time], y[end_time]}$

Solution 【动态规划】 ( 10ms)

执行用时: 10 ms, 在Grumpy Bookstore Owner的Java提交中击败了100.00% 的用户

内存消耗: 48.6 MB, 在Grumpy Bookstore Owner的Java提交中击败了100.00% 的用户

class Solution {
    public int maxSatisfied(int[] customers, int[] grumpy, int X) {
        int len = customers.length;
        int[] x = new int[len];
        int[] y = new int[len];
        /* base case */
        x[0] = customers[0] & (grumpy[0] - 1);
        y[0] = customers[0];
        int sum = customers[0];    // 优化使用技能期间的满意顾客总数
        /* dp */
        for (int i = 1; i < len; i++) {
            int v = customers[i] & (grumpy[i] - 1);
            x[i] = v + x[i-1];
            if (i < X) {
                sum += customers[i];
                y[i] = Math.max(y[i-1] + v, sum);
            } else {
                sum += customers[i] - customers[i-X];
                y[i] = Math.max(y[i-1]+ v, x[i-X] + sum);
            }
        }
        return Math.max(x[len-1], y[len-1]);
    }
}

复杂度分析

时间: O(n)

若不优化 sum 的存储,每次都重新计算,则为 O(n*X)

空间:O(1)