bugfix: s334 increasingTriplet

legolas.zhan · legolas.zhan · commit 784565fd265d · 2024-08-13T11:31:40.000+08:00
diff --git a/leetcode/array/increasingTriplet.go b/leetcode/array/increasingTriplet.go
@@ -20,26 +20,26 @@ Example 2:
 
 package larray
 
-func increasingTriplet(nums []int) bool {
-	left, right := -1, 0
-	for i := 1; i < len(nums); i++ {
-		if nums[i-1] >= nums[i] {
-			continue
-		}
+import "math"
 
-		if left < 0 {
-			left, right = i-1, i
-			continue
-		}
+func increasingTriplet(nums []int) bool {
+	if len(nums) < 3 {
+		return false
+	}
 
-		if nums[i-1] < nums[right] && nums[left] < nums[i-1] { // update right only
-			right = i - 1
+	min := nums[0]
+	minMid := math.MaxInt32
+	for i := 1; i < len(nums); i++ {
+		if nums[i] > minMid {
+			return true
 		}
-		if nums[i] < nums[right] { // need update all
-			left, right = i-1, i
+		if min > nums[i-1] {
+			min = nums[i-1]
 		}
-		if left >= 0 && nums[left] < nums[right] && nums[right] < nums[i] {
-			return true
+		if nums[i] > min {
+			if nums[i] < minMid {
+				minMid = nums[i]
+			}
 		}
 	}
 	return false
diff --git a/leetcode/array/increasingTriplet_test.go b/leetcode/array/increasingTriplet_test.go
@@ -17,4 +17,6 @@ func Test_increasingTriplet(t *testing.T) {
 	assert.False(increasingTriplet([]int{2, 1, 5, 0, 3}))
 	assert.True(increasingTriplet([]int{2, 1, 5, 0, 4, 6}))
 	assert.True(increasingTriplet([]int{1, 2, -10, -8, -7}))
+	assert.True(increasingTriplet([]int{0, 4, 1, -1, 2}))
+	assert.True(increasingTriplet([]int{20, 100, 10, 12, 5, 13}))
 }

Original file line number	Diff line number	Diff line change
`@@ -17,4 +17,6 @@ func Test_increasingTriplet(t *testing.T) {`
`17`	`17`	`assert.False(increasingTriplet([]int{2, 1, 5, 0, 3}))`
`18`	`18`	`assert.True(increasingTriplet([]int{2, 1, 5, 0, 4, 6}))`
`19`	`19`	`assert.True(increasingTriplet([]int{1, 2, -10, -8, -7}))`
	`20`	`+ assert.True(increasingTriplet([]int{0, 4, 1, -1, 2}))`
	`21`	`+ assert.True(increasingTriplet([]int{20, 100, 10, 12, 5, 13}))`
`20`	`22`	`}`