A
A
Algorithm Practice
Search…
A
A
Algorithm Practice
Introduction
Lintcode
Leetcode
Google
665 Non-decreasing Array
400 Nth Digit
484 Find Permutation
353 Design Snake Game
348 Design Tic-Tac-Toe
657 Judge Route Circle
789 Escape The Ghosts
667 Beautiful Arrangement II
359 Logger Rate Limiter
463 Island Perimeter
66 Plus One
249 Group Shifted Strings
281 Zigzag Iterator
54 Spiral Matrix
56 Merge Intervals
57 Insert Interval
163 Missing Ranges
228 Summary Ranges
166 Fraction to Recurring Decimal
780 Reaching Points
326 Power of Three
318 Maximum Product of Word Lengths
314 Binary Tree Vertical Order Traversal
297 Serialize and Deserialize Binary Tree
447 Number of Boomerangs
362 Design Hit Counter
448 Find All Numbers Disappeared in an Array
409 Longest Palindrome
406 Queue Reconstruction by Height
370 Range Addition
415 Add Strings
498 Diagonal Traverse
482 License Key Formatting
560 Subarray Sum Equals K
356 Line Reflection
748 Shortest Completing Word
218 The Skyline Problem
391 Perfect Rectangle
481 Magical String
380 Insert Delete GetRandom O(1)
800 Similar RGB Color
246 Strobogrammatic Number
247 Strobogrammatic Number II
465 Optimal Account Balancing
687 Longest Univalue Path
543 Diameter of Binary Tree
777 Swap Adjacent in LR String
792 Number of Matching Subsequences
460 LFU Cache
779 K-th Symbol in Grammar
289 Game of Life
31 Next Permutation
756 Pyramid Transition Matrix
753 Cracking the Safe
330 Patching Array
327 Count of Range Sum
769 Max Chunks To Make Sorted
768 Max Chunks To Make Sorted II
309 Best Time to Buy and Sell Stock with Cooldown
393 UTF-8 Validation
388 Longest Absolute File Path
807 Max Increase to Keep City Skyline
802 Find Eventual Safe States
469 Convex Polygon
683 K Empty Slots
157 Read N Characters Given Read4
158 Read N Characters Given Read4 II - Call multiple times
681 Next Closest Time
317 Shortest Distance from All Buildings
587 Erect the Fence
307 Range Sum Query - Mutable
308 Range Sum Query 2D - Mutable
282 Expression Add Operators
616 Add Bold Tag in String
497 Random Point in Non-overlapping Rectangles
544 Output Contest Matches
386 Lexicographical Numbers
Powered By
GitBook
665 Non-decreasing Array
665.
Non-decreasing Array
1. Question
Given an array with
n
integers, your task is to check if it could become non-decreasing by modifying
at most
1
element.
We define an array is non-decreasing if
array[i] <= array[i + 1]
holds for every
i
(1 <= i < n).
Example 1:
1
Input: [4,2,3]
2
3
Output: True
4
5
Explanation:
6
You could modify the first 4 to 1 to get a non-decreasing array.
Copied!
Example 2:
1
Input: [4,2,1]
2
3
Output: False
4
5
Explanation: You can't get a non-decreasing array by modify at most one element.
Copied!
Note:
The
n
belongs to [1, 10,000].
2. Implementation
(1) DP (TLE)
Longest Increasing Subsequence的思想
1
class
Solution
{
2
public
boolean
checkPossibility
(
int
[]
nums
)
{
3
if
(
nums
==
null
||
nums
.
length
<=
1
)
{
4
return
true
;
5
}
6
int
n
=
nums
.
length
;
7
int
[]
dp
=
new
int
[
n
];
8
Arrays
.
fill
(
dp
,
1
);
9
10
for
(
int
i
=
1
;
i
<
n
;
i
++
)
{
11
for
(
int
j
=
0
;
j
<
i
;
j
++
)
{
12
if
(
nums
[
j
]
<=
nums
[
i
]
&&
(
dp
[
j
]
+
1
>
dp
[
i
]))
{
13
dp
[
i
]
=
dp
[
j
]
+
1
;
14
}
15
}
16
}
17
18
int
maxLen
=
1
;
19
for
(
int
i
=
0
;
i
<
n
;
i
++
)
{
20
maxLen
=
Math
.
max
(
maxLen
,
dp
[
i
]);
21
}
22
return
maxLen
>=
n
-
1
;
23
}
24
}
Copied!
(2) Greedy
思路: 要使得整个数组是非递减,我们用一个prev变量记录
在nums[i]之前的最大数
,用count记录递减的次数,显然当count大于等于2时,我们无法修改一次数组使其递增。如果nums[i] < prev, 这里有两种情况决定如何更新prev:
1.如果nums[i - 2]不存在或者nums[i - 2] > nums[i]时,由于nums[i] < prev已经出现一次递减情况, 为了避免再出现一次递减,保证nums在[i -2, i]的非递减性, 我们不更新prev, 这等价于将nums[i]变成prev
2.如果nums[i - 2] <= nums[i],为了保证nums[i - 2, i]的非递减性, 我们将prev更新为nums[i]
1
class
Solution
{
2
public
boolean
checkPossibility
(
int
[]
nums
)
{
3
if
(
nums
==
null
||
nums
.
length
<=
1
)
{
4
return
true
;
5
}
6
7
int
n
=
nums
.
length
;
8
int
count
=
0
;
9
int
prev
=
nums
[
0
];
10
11
for
(
int
i
=
1
;
i
<
n
;
i
++
)
{
12
if
(
nums
[
i
]
<
prev
)
{
13
++
count
;
14
15
if
(
count
>=
2
)
{
16
return
false
;
17
}
18
19
if
(
i
-
2
>=
0
&&
nums
[
i
-
2
]
>
nums
[
i
])
continue
;
20
21
}
22
prev
=
nums
[
i
];
23
}
24
return
true
;
25
}
26
}
Copied!
3. Time & Space Complexity
DP
: 时间复杂度O(n^2), 空间复杂度O(n)
Greedy:
时间复杂度O(n^2), 空间复杂度O(n)
Previous
Google
Next
400 Nth Digit
Last modified
2yr ago
Copy link
Contents
665. Non-decreasing Array
1. Question
2. Implementation
3. Time & Space Complexity