334. Increasing triadic subsequences: An application of greedy solutions to the longest ascending subsequence (LIS) problem

Topic describes

This is a 334. Increasing triplet subsequence on LeetCode, of medium difficulty.

Tag: “LIS”, “longest ascending subsequence”, “greedy”, “dichotomy”

Given an integer array nums, determine if there is an increasing subsequence of length 333 in the array.

Return true if such a triplet subscript (I, j, k) exists and I < j < k such that nums[I] < nums[j] < nums[k]; Otherwise, return false.

Example 1:

Input: nums = [1,2,3,4,5] output: trueCopy the code

Example 2:

Input: nums = [5,4,3,2,1] output: false description: no triplet existsCopy the code

Example 3:

Input: nums = [2,1,5,0,4,6] output: true description: triples (3, 4, 5) satisfy the description because nums[3] == 0 < nums[4] == 4 < nums[5] == 6Copy the code

Tip:

• 
  $1 <= nums.length <= 5 * 10^5$
• 
  $-2^{31} <= nums[i] <= 2^{31} – 1$

Advanced: Can you implement a solution with time complexity O(nO(nO(n)) and space complexity O(1)O(1)O(1)?

Longest ascending subsequence (greedy + dichotomy)

We are asked to determine whether there is a ascending subsequence of length 333. The problem can be converted to finding the length of the longest ascending subsequence of numsnumsnums (LIS problem).

The answer to the original question is True if numsnumsnums has a maximum ascending subsequence length greater than or equal to 333, otherwise False.

O(nlog⁡n)O(n\log{n})O(nlogn) O(nlogn) is based on “greed + dichotomy”. The relationship between LCS problem and LIS problem, as well as the optimal solution proof of LIS problem, are explained in detail in LIS greedy solution proof, and the relationship with the longest common subsequence (LCS problem), which will not be repeated this time.

Basically, you’re going through every number
$nums[i]$At the same time, maintain a monotonic
$f[]$Array, where
$f[len] = x$Represents the length of
$len$The minimum ending element of the longest ascending subsequence of is
$x$It can be proved that
$f$Arrays are monotonic (seeFront 🧀), so less than can be found each time by dichotomy
$nums[i]$The maximum subscript of, to act as
$nums[i]$The first number of.

To sum up, we used LIS ‘” greedy + dichotomy “method to get the maximum length of the longest ascending subsequence, and then compared with 333 to get the answer.

Code (thanks@🍭 Cola Cola QAQOther languages provided by students) :

class Solution {
    public boolean increasingTriplet(int[] nums) {
        int n = nums.length, ans = 1;
        int[] f = new int[n + 1];
        Arrays.fill(f, 0x3f3f3f3f);
        for (int i = 0; i < n; i++) {
            int t = nums[i];
            int l = 1, r = i + 1;
            while (l < r) {
                int mid = l + r >> 1;
                if (f[mid] >= t) r = mid;
                else l = mid + 1;
            }
            f[r] = t;
            ans = Math.max(ans, r);
        }
        return ans >= 3; }}Copy the code

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int n = nums.size(), ans = 1;
        vector<int> f(n + 1, INT_MAX);
        for(int i = 0; i < n; i++){
            int t = nums[i];
            int L = 1, R = i + 1;
            while(L < R){
                int mid = L + R >> 1;
                if(f[mid] >= t) R = mid;
                else L = mid + 1;
            }
            f[R] = t;
            ans = max(ans, R);
        }
        return ans >= 3; }};Copy the code

• O(nlog⁡n)O(n\log{n})O(nlogn)
• Space complexity: O(n)O(n)O(n)

Optimization: fixed-length ascending subsequence (greedy)

In this case, we only need to determine whether there is an ascending subsequence of length 333, but do not need to answer the maximum length of LIS.

We can optimize the FFF array: A finite variable is used for substitution (the length of FFF array is compressed to 222), the meaning of the array remains unchanged, f[1]= Xf [1]=xf[1] =x indicates that the minimum ending element of the ascending subsequence of length 111 is XXX, F [2]=yf[2] =yf[2] =y indicates that the minimum ending element of the ascending subsequence with length 222 is YYy.

Scan each from front to back
$nums[i]$Every time, will
$nums[i]$Respectively with
$f[1]$ 和
$f[2]$Compare, if possible
$nums[i] > f[2]$On behalf of
$nums[i]$Can be connected at length of
$2$After the ascending subsequence of, returns directlyTrueOtherwise, try using
$nums[i]$To update the
$f[1]$ 和
$F [2].$

In this way, we only use finite variables. Nums [I]nums[I] only need to be compared with finite variables for each processing. The time complexity is O(n)O(n)O(n) O(1)O(1)O(1) O(1)O.

Code (thanks@🍭 Cola Cola QAQ 和 @BenhaoOther languages provided by students) :

class Solution {
    public boolean increasingTriplet(int[] nums) {
        int n = nums.length;
        long[] f = new long[3];
        f[1] = f[2] = (int)1e19;
        for (int i = 0; i < n; i++) {
            int t = nums[i];
            if (f[2] < t) return true;
            else if (f[1] < t && t < f[2]) f[2] = t;
            else if (f[1] > t) f[1] = t;
        }
        return false; }}Copy the code

class Solution:
    def increasingTriplet(self, nums: List[int]) - >bool:
        n = len(nums)
        f = [inf] * 3
        for i in range(n):
            t = nums[i]
            if f[2] < t:
                return True
            elif f[1] < t < f[2]:
                f[2] = t
            elif f[1] > t:
                f[1] = t
        return False
Copy the code

func increasingTriplet(nums []int) bool {
    n := len(nums)
    f := []int{math.MaxInt32,math.MaxInt32,math.MaxInt32}
    for i := 0; i < n; i++ {
        t := nums[i]
        if f[2] < t{
            return true
        } else if f[1] < t && t < f[2]{
            f[2] = t
        } else if f[1] > t {
            f[1] = t
        }
    }
    return false
}
Copy the code

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int n = nums.size(a);vector<int> f(3, INT_MAX);
        for(int i = 0; i < n; i++){
            int t = nums[i];
            if(f[2] < t) return true;
            else if(f[1] < t and t < f[2]) f[2] = t;
            else if(f[1] > t) f[1] = t;
        }
        return false; }};Copy the code

• Time complexity: O(n)O(n)O(n)
• Space complexity: O(1)O(1)O(1)

The last

This is the no.334 article in our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 questions in LeetCode as of the start date, some of which have locks. We will finish all the questions without locks first.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.