{"id":5214,"date":"2019-05-27T01:02:13","date_gmt":"2019-05-27T08:02:13","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5214"},"modified":"2019-05-27T01:04:34","modified_gmt":"2019-05-27T08:04:34","slug":"leetcode-1052-grumpy-bookstore-owner","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/sliding-window\/leetcode-1052-grumpy-bookstore-owner\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1052. Grumpy Bookstore Owner"},"content":{"rendered":"\n<p>Today, the bookstore owner has a store open for&nbsp;<code>customers.length<\/code>&nbsp;minutes.&nbsp; Every minute, some number of customers (<code>customers[i]<\/code>) enter the store, and all those customers leave after the end of that minute.<\/p>\n\n\n\n<p>On some minutes, the bookstore owner is grumpy.&nbsp; If the bookstore owner is grumpy on the i-th minute,&nbsp;<code>grumpy[i] = 1<\/code>, otherwise&nbsp;<code>grumpy[i] = 0<\/code>.&nbsp; When the bookstore owner is grumpy, the customers of that minute are not satisfied, otherwise they are satisfied.<\/p>\n\n\n\n<p>The bookstore owner knows a secret technique to keep themselves&nbsp;not grumpy for&nbsp;<code>X<\/code>&nbsp;minutes straight, but can only use it once.<\/p>\n\n\n\n<p>Return the maximum number of customers that can be satisfied throughout the day.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted; crayon:false\"><strong>Input: <\/strong>customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3\n<strong>Output: <\/strong>16\n<strong>Explanation:<\/strong>&nbsp;The bookstore owner keeps themselves&nbsp;not grumpy for the last 3 minutes. \nThe maximum number of customers that can be satisfied = 1 + 1 + 1 + 1 + 7 + 5 = 16.\n<\/pre>\n\n\n\n<p><strong>Note:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= X &lt;=&nbsp;customers.length ==&nbsp;grumpy.length &lt;= 20000<\/code><\/li><li><code>0 &lt;=&nbsp;customers[i] &lt;= 1000<\/code><\/li><li><code>0 &lt;=&nbsp;grumpy[i] &lt;= 1<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Sliding Window<\/strong><\/h2>\n\n\n\n<p>Sum the costumers of  non grumpy minutes, recording the max sum of the sliding window of size X.<\/p>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: o(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X) {    \n    int base = 0;\n    int window = 0;\n    int best_window = 0;    \n    for (int i = 0; i < grumpy.size(); ++i) {\n      (grumpy[i] ? window : base) += customers[i];        \n      if (i >= X && grumpy[i - X])\n        window -= customers[i - X];\n      best_window = max(best_window, window);\n    }\n    return base + best_window;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Today, the bookstore owner has a store open for&nbsp;customers.length&nbsp;minutes.&nbsp; Every minute, some number of customers (customers[i]) enter the store, and all those customers leave after&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[476],"tags":[177,215],"class_list":["post-5214","post","type-post","status-publish","format-standard","hentry","category-sliding-window","tag-medium","tag-sliding-window","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5214","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=5214"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5214\/revisions"}],"predecessor-version":[{"id":5217,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5214\/revisions\/5217"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5214"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5214"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5214"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}