Created
August 15, 2018 06:04
-
-
Save jianminchen/f6deab57fd1572d6cd3fffff0fb88a66 to your computer and use it in GitHub Desktop.
Leetcode 665 - Non decreasing array
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace Leetcode_665_Non_decreasing_array | |
{ | |
class Program | |
{ | |
static void Main(string[] args) | |
{ | |
var result = CheckPossibility(new int[] { 2, 3, 3, 2, 4 }); | |
} | |
/// <summary> | |
/// time complexity O(N), N is the length of the array | |
/// compare a node with next, if it is bigger than next, count increments one; | |
/// and then check the previous with the next one, if it is decreasing, then return false. | |
/// At most one case a node is bigger than next. | |
/// </summary> | |
/// <param name="nums"></param> | |
/// <returns></returns> | |
public static bool CheckPossibility(int[] nums) | |
{ | |
if (nums == null) | |
return true; | |
var length = nums.Length; | |
if (length == 1) | |
return true; | |
var count = 0; | |
for(int i = 0; i < length; i++) | |
{ | |
var current = nums[i]; | |
if(i + 1 < length && current > nums[i + 1]) | |
{ | |
count++; | |
// two user cases: -1, 4, 2, 3, | |
// index = 1, one is to replace index = 1 or index = 2 | |
// replace index = i + 1 | |
if(( i + 2 < length && nums[i] > nums[i + 2]) && | |
// replce index = i | |
( i > 0 && nums[i - 1] > nums[i + 1])) | |
{ | |
return false; | |
} | |
} | |
if (count >= 2) | |
return false; | |
} | |
return true; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment