{"id":9136,"date":"2021-12-12T10:54:07","date_gmt":"2021-12-12T18:54:07","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9136"},"modified":"2021-12-12T10:54:57","modified_gmt":"2021-12-12T18:54:57","slug":"leetcode-2100-find-good-days-to-rob-the-bank","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/leetcode-2100-find-good-days-to-rob-the-bank\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2100. Find Good Days to Rob the Bank"},"content":{"rendered":"\n<p>You and a gang of thieves are planning on robbing a bank. You are given a&nbsp;<strong>0-indexed<\/strong>&nbsp;integer array&nbsp;<code>security<\/code>, where&nbsp;<code>security[i]<\/code>&nbsp;is the number of guards on duty on the&nbsp;<code>i<sup>th<\/sup><\/code>&nbsp;day. The days are numbered starting from&nbsp;<code>0<\/code>. You are also given an integer&nbsp;<code>time<\/code>.<\/p>\n\n\n\n<p>The&nbsp;<code>i<sup>th<\/sup><\/code>&nbsp;day is a good day to rob the bank if:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>There are at least&nbsp;<code>time<\/code>&nbsp;days before and after the&nbsp;<code>i<sup>th<\/sup><\/code>&nbsp;day,<\/li><li>The number of guards at the bank for the&nbsp;<code>time<\/code>&nbsp;days&nbsp;<strong>before<\/strong>&nbsp;<code>i<\/code>&nbsp;are&nbsp;<strong>non-increasing<\/strong>, and<\/li><li>The number of guards at the bank for the&nbsp;<code>time<\/code>&nbsp;days&nbsp;<strong>after<\/strong>&nbsp;<code>i<\/code>&nbsp;are&nbsp;<strong>non-decreasing<\/strong>.<\/li><\/ul>\n\n\n\n<p>More formally, this means day&nbsp;<code>i<\/code>&nbsp;is a good day to rob the bank if and only if&nbsp;<code>security[i - time] &gt;= security[i - time + 1] &gt;= ... &gt;= security[i] &lt;= ... &lt;= security[i + time - 1] &lt;= security[i + time]<\/code>.<\/p>\n\n\n\n<p>Return&nbsp;<em>a list of&nbsp;<strong>all<\/strong>&nbsp;days&nbsp;<strong>(0-indexed)&nbsp;<\/strong>that are good days to rob the bank<\/em>.<em>&nbsp;The order that the days are returned in does<strong>&nbsp;<\/strong><strong>not<\/strong>&nbsp;matter.<\/em><\/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> security = [5,3,3,3,5,6,2], time = 2\n<strong>Output:<\/strong> [2,3]\n<strong>Explanation:<\/strong>\nOn day 2, we have security[0] &gt;= security[1] &gt;= security[2] &lt;= security[3] &lt;= security[4].\nOn day 3, we have security[1] &gt;= security[2] &gt;= security[3] &lt;= security[4] &lt;= security[5].\nNo other days satisfy this condition, so days 2 and 3 are the only good days to rob the bank.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> security = [1,1,1,1,1], time = 0\n<strong>Output:<\/strong> [0,1,2,3,4]\n<strong>Explanation:<\/strong>\nSince time equals 0, every day is a good day to rob the bank, so return every day.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> security = [1,2,3,4,5,6], time = 2\n<strong>Output:<\/strong> []\n<strong>Explanation:<\/strong>\nNo day has 2 days before it that have a non-increasing number of guards.\nThus, no day is a good day to rob the bank, so return an empty list.\n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> security = [1], time = 5\n<strong>Output:<\/strong> []\n<strong>Explanation:<\/strong>\nNo day has 5 days before and after it.\nThus, no day is a good day to rob the bank, so return an empty list.<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= security.length &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>0 &lt;= security[i], time &lt;= 10<sup>5<\/sup><\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Pre-Processing<\/strong><\/h2>\n\n\n\n<p>Pre-compute the non-increasing days at days[i] and the non-decreasing days at days[i] using prefix and suffix arrays.<\/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  vector<int> goodDaysToRobBank(vector<int>& security, int time) {\n    const int n = security.size();\n    vector<int> before(n);\n    vector<int> after(n);\n    for (int i = 1; i < n; ++i)\n      before[i] = security[i - 1] >= security[i] ? before[i - 1] + 1 : 0;\n    for (int i = n - 2; i >= 0; --i)\n      after[i] = security[i + 1] >= security[i] ? after[i + 1] + 1 : 0;\n    vector<int> ans;\n    for (int i = time; i + time < n; ++i)\n      if (before[i] >= time && after[i] >= time)\n        ans.push_back(i);\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You and a gang of thieves are planning on robbing a bank. You are given a&nbsp;0-indexed&nbsp;integer array&nbsp;security, where&nbsp;security[i]&nbsp;is the number of guards on duty on&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184],"tags":[20,177,97,186],"class_list":["post-9136","post","type-post","status-publish","format-standard","hentry","category-array","tag-array","tag-medium","tag-prefix","tag-suffix","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9136","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=9136"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9136\/revisions"}],"predecessor-version":[{"id":9138,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9136\/revisions\/9138"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9136"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9136"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9136"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}