java - 【算法题】给定int数组，移除不超过一个元素后，判断是否存在自增序列

Question

没什么思路啊，题目如下
Given a sequence of integers as an array, determine whether it is possible to obtain a strictly increasing sequence by removing no more than one element from the array.

Example

For sequence = [1, 3, 2, 1], the output should be
almostIncreasingSequence(sequence) = false;

There is no one element in this array that can be removed in order to get a strictly increasing sequence.

For sequence = [1, 3, 2], the output should be
almostIncreasingSequence(sequence) = true.

You can remove 3 from the array to get the strictly increasing sequence [1, 2]. Alternately, you can remove 2 to get the strictly increasing sequence [1, 3].

Input/Output

[time limit] 4000ms (js)
[input] array.integer sequence

Guaranteed constraints:
2 ≤ sequence.length ≤ 105,
-105 ≤ sequence[i] ≤ 105.

[output] boolean

Return true if it is possible to remove one element from the array in order to get a strictly increasing sequence, otherwise return false.

有个思路：2层循环，第一循环移除元素，第二层循环判断移除这个元素后是否有自增序列。

Answer 1

아이디어 제공

차이별 배열을 만듭니다. 예를 들어 a=[1,3,2,1]이고 차이별 배열 후에는 [2,-1,-1]을 얻습니다.

소위 요소 삭제란 차이별 배열에서 머리 또는 꼬리를 제거하거나 인접한 두 요소를 하나의 요소에 추가하는 것을 의미합니다.

따라서 차이 배열에 음수가 두 개 이상 있으면 작동하지 않으며, 음수가 없으면 작동합니다. 삭제하거나 양수로 병합할 수 있습니다.

이런 방식으로 시간 복잡도를 O(n)으로 줄일 수 있습니다

Answer 2

O(n) 시간에 수행 가능:

1. 인접한 각 [a, b]에 대해 a >= b인지 확인합니다. 이러한 숫자 쌍은 엄격한 증분성을 파괴합니다. 그러한 쌍이 두 개 이상 있으면 false를 반환합니다. 아무것도 없으면 true를 반환합니다.

2. 1에 [a0, b0] 쌍이 하나만 있는 경우 "a0 또는 b0을 제거한 후에도 여전히 증가하는지 여부"를 확인하고

을 반환합니다.

Answer 3

결과는 정확하지만, 지정된 시간을 초과했습니다. 더 좋은 방법이 있나요?

으아악

시간 복잡도가 O(n)인 방법

으아악

Answer 4

이건 역수를 세는 건가요?