Description#
You are given a 0-indexed integer array nums of size n and a positive integer k.
We call an index i in the range k <= i < n - k good if the following conditions are satisfied:
- The
k elements that are just before the index i are in non-increasing order. - The
k elements that are just after the index i are in non-decreasing order.
Return an array of all good indices sorted in increasing order.
Example 1:
Input: nums = [2,1,1,1,3,4,1], k = 2
Output: [2,3]
Explanation: There are two good indices in the array:
- Index 2. The subarray [2,1] is in non-increasing order, and the subarray [1,3] is in non-decreasing order.
- Index 3. The subarray [1,1] is in non-increasing order, and the subarray [3,4] is in non-decreasing order.
Note that the index 4 is not good because [4,1] is not non-decreasing.
Example 2:
Input: nums = [2,1,1,2], k = 2
Output: []
Explanation: There are no good indices in this array.
Constraints:
n == nums.length3 <= n <= 1051 <= nums[i] <= 1061 <= k <= n / 2
Solutions#
Solution 1: Recursion#
We define two arrays decr and incr, which represent the longest non-increasing and non-decreasing subarray lengths from left to right and from right to left, respectively.
We traverse the array, updating the decr and incr arrays.
Then we sequentially traverse the index $i$ (where $k\le i \lt n - k$), if $decr[i] \geq k$ and $incr[i] \geq k$, then $i$ is a good index.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array.
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution:
def goodIndices(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
decr = [1] * (n + 1)
incr = [1] * (n + 1)
for i in range(2, n - 1):
if nums[i - 1] <= nums[i - 2]:
decr[i] = decr[i - 1] + 1
for i in range(n - 3, -1, -1):
if nums[i + 1] <= nums[i + 2]:
incr[i] = incr[i + 1] + 1
return [i for i in range(k, n - k) if decr[i] >= k and incr[i] >= k]
|
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
| class Solution {
public List<Integer> goodIndices(int[] nums, int k) {
int n = nums.length;
int[] decr = new int[n];
int[] incr = new int[n];
Arrays.fill(decr, 1);
Arrays.fill(incr, 1);
for (int i = 2; i < n - 1; ++i) {
if (nums[i - 1] <= nums[i - 2]) {
decr[i] = decr[i - 1] + 1;
}
}
for (int i = n - 3; i >= 0; --i) {
if (nums[i + 1] <= nums[i + 2]) {
incr[i] = incr[i + 1] + 1;
}
}
List<Integer> ans = new ArrayList<>();
for (int i = k; i < n - k; ++i) {
if (decr[i] >= k && incr[i] >= k) {
ans.add(i);
}
}
return ans;
}
}
|
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
| class Solution {
public:
vector<int> goodIndices(vector<int>& nums, int k) {
int n = nums.size();
vector<int> decr(n, 1);
vector<int> incr(n, 1);
for (int i = 2; i < n; ++i) {
if (nums[i - 1] <= nums[i - 2]) {
decr[i] = decr[i - 1] + 1;
}
}
for (int i = n - 3; ~i; --i) {
if (nums[i + 1] <= nums[i + 2]) {
incr[i] = incr[i + 1] + 1;
}
}
vector<int> ans;
for (int i = k; i < n - k; ++i) {
if (decr[i] >= k && incr[i] >= k) {
ans.push_back(i);
}
}
return ans;
}
};
|
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
| func goodIndices(nums []int, k int) []int {
n := len(nums)
decr := make([]int, n)
incr := make([]int, n)
for i := range decr {
decr[i] = 1
incr[i] = 1
}
for i := 2; i < n; i++ {
if nums[i-1] <= nums[i-2] {
decr[i] = decr[i-1] + 1
}
}
for i := n - 3; i >= 0; i-- {
if nums[i+1] <= nums[i+2] {
incr[i] = incr[i+1] + 1
}
}
ans := []int{}
for i := k; i < n-k; i++ {
if decr[i] >= k && incr[i] >= k {
ans = append(ans, i)
}
}
return ans
}
|
