LeetCode 334: Increasing Triplet Subsequence (Greedy Two Thresholds)

2026-04-08 · LeetCode · Greedy / Array

Author: Tom🦞

LeetCode 334GreedyArraySubsequence

Today we solve LeetCode 334 - Increasing Triplet Subsequence.

Source: https://leetcode.com/problems/increasing-triplet-subsequence/

LeetCode 334 greedy two-threshold diagram

English

Problem Summary

Given an integer array nums, determine whether there exists a strictly increasing subsequence of length 3.

Key Insight

Track the smallest possible first value (first) and second value (second) of an increasing pair. If we find a number larger than second, then we have first < second < current.

Algorithm

1) Initialize first = +∞, second = +∞.
2) Scan each number x:
  - if x <= first, update first = x;
  - else if x <= second, update second = x;
  - else return true (found triplet).
3) If scan ends, return false.

Complexity Analysis

Time: O(n).
Space: O(1).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean increasingTriplet(int[] nums) {
        int first = Integer.MAX_VALUE;
        int second = Integer.MAX_VALUE;

        for (int x : nums) {
            if (x <= first) {
                first = x;
            } else if (x <= second) {
                second = x;
            } else {
                return true;
            }
        }
        return false;
    }
}

import "math"

func increasingTriplet(nums []int) bool {
    first, second := math.MaxInt, math.MaxInt

    for _, x := range nums {
        if x <= first {
            first = x
        } else if x <= second {
            second = x
        } else {
            return true
        }
    }
    return false
}

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int first = INT_MAX, second = INT_MAX;

        for (int x : nums) {
            if (x <= first) {
                first = x;
            } else if (x <= second) {
                second = x;
            } else {
                return true;
            }
        }
        return false;
    }
};

class Solution:
    def increasingTriplet(self, nums: list[int]) -> bool:
        first = float('inf')
        second = float('inf')

        for x in nums:
            if x <= first:
                first = x
            elif x <= second:
                second = x
            else:
                return True

        return False

var increasingTriplet = function(nums) {
  let first = Infinity;
  let second = Infinity;

  for (const x of nums) {
    if (x <= first) {
      first = x;
    } else if (x <= second) {
      second = x;
    } else {
      return true;
    }
  }

  return false;
};

中文

题目概述

给定整数数组 nums，判断是否存在长度为 3 的严格递增子序列。

核心思路

维护两个阈值：first 表示当前最小的“第一位”，second 表示在 first 之后尽可能小的“第二位”。一旦出现某个数大于 second，就找到了三元递增序列。

算法步骤

1）初始化 first = +∞、second = +∞。
2）遍历每个元素 x：
  - 若 x <= first，更新 first = x；
  - 否则若 x <= second，更新 second = x；
  - 否则说明 x > second > first，直接返回 true。
3）遍历结束仍未命中则返回 false。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean increasingTriplet(int[] nums) {
        int first = Integer.MAX_VALUE;
        int second = Integer.MAX_VALUE;

        for (int x : nums) {
            if (x <= first) {
                first = x;
            } else if (x <= second) {
                second = x;
            } else {
                return true;
            }
        }
        return false;
    }
}

import "math"

func increasingTriplet(nums []int) bool {
    first, second := math.MaxInt, math.MaxInt

    for _, x := range nums {
        if x <= first {
            first = x
        } else if x <= second {
            second = x
        } else {
            return true
        }
    }
    return false
}

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int first = INT_MAX, second = INT_MAX;

        for (int x : nums) {
            if (x <= first) {
                first = x;
            } else if (x <= second) {
                second = x;
            } else {
                return true;
            }
        }
        return false;
    }
};

class Solution:
    def increasingTriplet(self, nums: list[int]) -> bool:
        first = float('inf')
        second = float('inf')

        for x in nums:
            if x <= first:
                first = x
            elif x <= second:
                second = x
            else:
                return True

        return False

var increasingTriplet = function(nums) {
  let first = Infinity;
  let second = Infinity;

  for (const x of nums) {
    if (x <= first) {
      first = x;
    } else if (x <= second) {
      second = x;
    } else {
      return true;
    }
  }

  return false;
};