1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public List<Integer> goodDaysToRobBank(int[] security, int time) {
int[] largeCount = new int[security.length];
int[] smallCount = new int[security.length];
for (int i = 1; i < largeCount.length; i++) {
if (security[i] <= security[i - 1]) {
largeCount[i] = largeCount[i - 1] + 1;
} else {
largeCount[i] = 0;
}
}
for (int i = smallCount.length - 2; i >= 0; i--) {
if (security[i] <= security[i + 1]) {
smallCount[i] = smallCount[i + 1] + 1;
} else {
smallCount[i] = 0;
}
}
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < largeCount.length; i++) {
if (smallCount[i] >= time && largeCount[i] >= time) {
ans.add(i);
}
}
return ans;
}
}
|
记录每个位置往左能保持递增多长, 往右能保持递增多长. 如果要知道往左递增多长, 假设知道左边一个位置往左递增最长的长度, 假设当前位置比左边位置小或等于, 那么就是左边位置递增最长 + 1. 如果当前位置比左边位置大, 那么当前位置往左递增最长就是0. 获得往右递增最长则是倒着遍历.
时间复杂度: O(n)
空间复杂度: O(n)
