Bei einem ganzzahligen Array nums wird die Länge des längsten streng ansteigenden
zurückgegeben Folge
.
Beispiel 1:
Eingabe: nums = [10,9,2,5,3,7,101,18]
Ausgabe: 4
Erläuterung: Die längste ansteigende Teilfolge ist [2,3,7,101], daher beträgt die Länge 4,
Beispiel 2:
Eingabe: nums = [0,1,0,3,2,3]
Ausgabe: 4
Beispiel 3:
Eingabe: nums = [7,7,7,7,7,7,7]
Ausgabe: 1
Einschränkungen:
1 <= nums.length <= 2500
-10^4 <= nums[i] <= 10^4
Follow-up: Können Sie einen Algorithmus entwickeln, der mit einer Zeitkomplexität von O(n log(n)) ausgeführt wird?
Originalseite
public int lengthOfLIS(int[] nums) { int start = nums[0]; int pre = nums[0]; int preMax = nums[0]; int cnt = 1; int max = 1; for(int i=1; ipre){ cnt ++; } pre = nums[i]; System.out.println("cur:"+nums[i] + " pre:"+pre+ " count:" + cnt); } return Math.max(max, cnt); } Fehler beheben
Nach dem Login kopierenNach dem Login kopieren
public int lengthOfLIS(int[] nums) { TreeMapmap = new TreeMap<>(); map.put(Integer.MIN_VALUE,0); for(int i: nums) { map.put(i,map.get(map.lowerKey(i))+1); while(map.higherKey(i)!=null && map.get(map.higherKey(i))<=map.get(i)) { map.remove(map.higherKey(i)); } } return map.get(map.lastKey()); }
Gibt bei einem unsortierten Array ganzzahliger Zahlen die Länge der längsten kontinuierlich ansteigenden Teilsequenz (d. h. Subarray) zurück. Die Teilfolge muss streng ansteigend sein.
Eine kontinuierlich steigende Teilfolge wird durch zwei Indizes l und r (l < r) definiert, sodass sie [nums[l], nums[l + 1], ..., nums[r - 1], nums[r ist ]] und für jedes l <= i < r, nums[i] < nums[i + 1].
Beispiel 1:
Eingabe: nums = [1,3,5,4,7]
Ausgabe: 3
Erläuterung: Die längste kontinuierlich ansteigende Teilfolge ist [1,3,5] mit der Länge 3.
Obwohl [1,3,5,7] eine aufsteigende Teilfolge ist, ist sie nicht stetig, da die Elemente 5 und 7 durch Elemente getrennt sind
4.
Beispiel 2:
Eingabe: nums = [2,2,2,2,2]
Ausgabe: 1
Erläuterung: Die längste kontinuierlich ansteigende Teilfolge ist [2] mit der Länge 1. Beachten Sie, dass sie streng sein muss
zunehmend.
Einschränkungen:
1 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
Originalseite
public int findLengthOfLCIS(int[] nums) { if(nums.length < 1){ return 0; } int res = 1; int cnt = 1; int pre = nums[0]; for(int i=1; ipre){ cnt++; }else{ res = Math.max(res, cnt); cnt = 1; } // System.out.println("cur: " + nums[i] + " pre:" + pre + " count:" + cnt); pre = nums[i]; } return Math.max(res, cnt); }
Anders als bei der vorherigen Frage konnten wir bei dieser Frage nur kontinuierlich steigende Teilsequenzen berücksichtigen, was den Prozess vereinfacht.
Das obige ist der detaillierte Inhalt vonLeetCode Day Dynamische Programmierung Teil 10. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!