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] が得られます

いわゆる要素の削除とは、差分配列の先頭または末尾を削除すること、または 2 つの隣接する要素を 1 つの要素に追加することを意味します。

したがって、差分配列に複数の負の数がある場合は機能しませんが、負の数が存在しない場合は、負の数が存在する場合のみ上記の操作が実行されます。削除するか正の数にマージすると機能します

このようにして、時間計算量は O(n) に削減できます

Answer 2

O(n) 時間で実行可能:O(n) 时间做到:

1. 对每个相邻的 [a, b]，判断是否 a >= b。这样的数对破坏严格递增性。如果这样的数对超过一个，返回false。如果一个也没有，返回true。

2. 如果1中只有一对 [a0, b0]，判断 "移除a0或b0

3. 隣接する各 [a, b] について、a >= b かどうかを判断します。このような数値のペアは厳密な増分性を破壊します。そのようなペアが複数ある場合は、false を返します。何もない場合は true を返します。

🎜1 に [a0, b0] のペアが 1 つしかない場合、「a0 または b0 を削除した後も増加するかどうか」を判断します。 >」と返します 🎜🎜 🎜

Answer 3

結果は正しいですが、指定された時間を超えています。もっと良い方法はありますか?

リーリー

時間計算量が O(n) のメソッド

リーリー

Answer 4

これは逆数の数を数えているのでしょうか？