力杨网站建设,wordpress 注册推广,wordpress cart插件,百度竞价广告的位置题目链接 Leetcode.2100 适合打劫银行的日子 Rating #xff1a; 1702 题目描述
你和一群强盗准备打劫银行。给你一个下标从 0开始的整数数组 security#xff0c;其中 security[i]是第 i天执勤警卫的数量。日子从 0开始编号。同时给你一个整数 time。
如果第 i天满足以下所…题目链接 Leetcode.2100 适合打劫银行的日子 Rating 1702 题目描述
你和一群强盗准备打劫银行。给你一个下标从 0开始的整数数组 security其中 security[i]是第 i天执勤警卫的数量。日子从 0开始编号。同时给你一个整数 time。
如果第 i天满足以下所有条件我们称它为一个适合打劫银行的日子
第 i天前和后都分别至少有 time天。第 i天前连续 time天警卫数目都是非递增的。第 i天后连续 time天警卫数目都是非递减的。
更正式的第 i天是一个合适打劫银行的日子当且仅当security[i - time] security[i - time 1] ... security[i] ... security[i time - 1] security[i time].
请你返回一个数组包含 所有 适合打劫银行的日子下标从 0开始。返回的日子可以 任意 顺序排列。
示例 1 输入security [5,3,3,3,5,6,2], time 2 输出[2,3] 解释 第 2 天我们有 security[0] security[1] security[2] security[3] security[4] 。 第 3 天我们有 security[1] security[2] security[3] security[4] security[5] 。 没有其他日子符合这个条件所以日子 2 和 3 是适合打劫银行的日子。 示例 2 输入security [1,1,1,1,1], time 0 输出[0,1,2,3,4] 解释 因为 time 等于 0 所以每一天都是适合打劫银行的日子所以返回每一天。 示例 3 输入security [1,2,3,4,5,6], time 2 输出[] 解释 没有任何一天的前 2 天警卫数目是非递增的。 所以没有适合打劫银行的日子返回空数组。 提示
1security.length1051 security.length 10^51security.length1050security[i],time1050 security[i], time 10^50security[i],time105
分析
适合打劫的那天 security[i]包括第 i天在内前 time1天是非递增的后 time1天是非递减的。
我们使用 前后缀分解 求解本题。
定义两个数组 left,right。
left[i]表示以 security[i]结尾非递增的连续天数。right[i]表示以 security[i]结尾非递减的连续天数。
我们能够遍历的合法区间是 [time,n-time-1]。只要在这个区间内left[i] time1 right[i] time1说明第 i天是适合打劫的。
时间复杂度:O(n)O(n)O(n)
C代码
class Solution {
public:vectorint goodDaysToRobBank(vectorint security, int time) {int n security.size();vectorint left(n),right(n);left[0] 1;for(int i 1;i n;i){left[i] 1;if(security[i-1] security[i]) left[i] left[i-1];}right[n-1] 1;for(int i n - 2;i 0;i--){right[i] 1;if(security[i1] security[i]) right[i] right[i1];}vectorint ans;for(int i time;i n - time;i){if(left[i] time 1 right[i] time 1) ans.push_back(i);}return ans;}
};Java代码
class Solution {public ListInteger goodDaysToRobBank(int[] security, int time) {int n security.length;int[] left new int[n];int[] right new int[n];left[0] 1;for(int i 1;i n;i){left[i] 1;if(security[i-1] security[i]) left[i] left[i-1];}right[n-1] 1;for(int i n - 2;i 0;i--){right[i] 1;if(security[i1] security[i]) right[i] right[i1];}ListInteger res new ArrayList();for(int i time;i n - time;i){if(left[i] time 1 right[i] time 1) res.add(i);}return res;}
}
