This article has participated in the activity of “New person creation Ceremony”, and started the road of digging gold creation together.

preface

Today, I finished leetcode’s problem of the day and learned the idea of divide and conquer for greedy algorithms.

Topic describes

Today’s topic is 334 on LeetCode. Increasing triplet subsequences are of medium difficulty

  • Given an array of integers, nums, determine if there is an increasing subsequence of length 3 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:

Enter: nums = [1.2.3.4.5] output:trueAny triplet of I < j < k satisfies the above descriptionCopy the code

Example 2:

Enter: nums = [5.4.3.2.1] output:falseExplanation: There are no triples that satisfy the questionCopy the code

Example 3:

Enter: nums = [2.1.5.0.4.6] output:trueExplanation: Triples (3.4.5) 满足题意，因为 nums[3] = =0 < nums[4] = =4 < nums[5] = =6
Copy the code

Tip:

  • 1 <= nums.length <= 5 * 105
  • -231 <= nums[i] <= 231 – 1

 

  • Advanced: Can you implement a time complexity O(n), space complexity O(1) solution?

Greedy algorithm

The basic idea of greedy algorithm is that if a problem cannot find its optimal solution temporarily, it can be considered to break it into several small problems, respectively to find the optimal solution of each small problem, and then stack them up as the “optimal solution” of the whole problem.

Three steps of a greedy algorithm

  1. What is the optimal solution that we need

  2. Analyze the subproblem and determine the optimal solution of the subproblem

  3. Find the optimal solution of each subproblem and then add up the global optimal solution

Examples of greedy algorithms

A classic example of greedy algorithms is the knapsack problem:

There is a backpack that can carry up to 150 kg of weight. Now there are 7 items with weights of [35, 30, 60, 50, 40, 10, 25] and their value is [10, 40, 30, 50, 35, 40, 30]. How should we choose to carry the most valuable items in our backpack?

  1. First, identify the optimal solution we need to take away the item with the most value
  2. The local optimal solution has many different choices, can choose the highest value, or the lightest weight, or the most cost-effective
  3. Choose different items according to your choice

usage

  1. The global optimal solution is not easy to obtain
  2. The mathematical model of global optimal solution is difficult to establish
  3. There is no need to obtain an optimal solution, you can accept a relatively optimal solution that is close to the optimal

After a brief introduction of greedy algorithms, let’s go back to the problem

Answer key

Analysis of the

We’re going to ask for an increasing subsequence of three, and we’re going to find that it’s not easy to find a increasing subsequence of three, but we can fix two subsequences that are increasing in size and index, and then iterate to find the third one that is.

This is using the idea of greedy algorithm, three sub-sequences are hard to find, then split the problem, first to find two sub-sequences that meet the conditions, and then to find the third.

So we maintain two variables, first and second, that represent the first and second of an increasing triplet subsequence, and always satisfy first<second. The array NUMs is then iterated to find the third number that satisfies the condition.

At initialization, first = nums[0], second = +∞, each traversal performs the following lookup:

  1. If num[I] > second, we have found the third number we need, return true
  2. If num[I] > first, update second
  3. If num[I] is smaller than either of the present numbers, assign first

If no third number is found, the array does not exist. Return false

If second is followed by a value less than second, then the index of first will be greater than second. It doesn’t matter, because we know that there was a number less than second before that, so even if a third number appears immediately after that, There will still be a triadic subsequence that satisfies the condition, and it will return true

code

/ * * *@param {number[]} nums
 * @return {boolean}* /
var increasingTriplet = function(nums) {
    if (nums.length < 3) {
        return false;
    }
    let first = nums[0], second = Number.MAX_VALUE;
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] > second) {
            return true;
        } else if (nums[i] > first) {
            second = nums[i];
        } else{ first = nums[i]; }}return false;
};

Copy the code