题目

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.

Note: Your algorithm should run in O(n) time complexity and O(1) space complexity.

Example 1:

  1. Input: [1,2,3,4,5]
  2. Output: true

Example 2:

  1. Input: [5,4,3,2,1]
  2. Output: false

题意

判断给定数组中是否存在一组下标为i、j、k的数，满足i<j<k且arr[i]<arr[j]<arr[k]。要求时间复杂度为0334. Increasing Triplet Subsequence (M) - 图1且空间复杂度为0334. Increasing Triplet Subsequence (M) - 图2。

思路

如果没有空间复杂度的要求，比较容易想到的方法是再建两个数组leftMax和rightMin，leftMax[i]表示从首元素到i中最大的数，rightMin[j]表示从j到末元素中最小的数，如果存在leftMax[i]<arr[i]<rightMin[i]，说明存在满足条件的三元组。

为了满足0334. Increasing Triplet Subsequence (M) - 图3的空间复杂度要求，可以这样实现：设两个变量small和mid，从左向右遍历数组，如果arr[i]<=small，更新small，否则如果arr[i]<=mid，更新mid，这样当遍历到下标为i的数时，small表示0-(i-1)中最小的数，mid表示0-(i-1)中第二小的数 (描述的是存在关系，具体的相对位置不一定正确)，只要arr[i]>mid，说明就能构成严格递增的三元组。

代码实现

Java

  1. class Solution {
  2.     public boolean increasingTriplet(int[] nums) {
  3.         int small = Integer.MAX_VALUE, mid = Integer.MAX_VALUE;
  4.         for (int num : nums) {
  5.             if (num <= small) {
  6.                 small = num;
  7.             } else if (num <= mid) {
  8.                 mid = num;
  9.             } else {
  10.                 return true;
  11.             }
  12.         }
  13.         return false;
  14.     }
  15. }

JavaScript

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {boolean}
  4.  */
  5. var increasingTriplet = function (nums) {
  6.   let lessLeft = []
  7.   let compare = Infinity
  9.   for (let num of nums) {
  10.     lessLeft.push(compare < num ? true : false)
  11.     compare = Math.min(compare, num)
  12.   }
  14.   compare = -Infinity
  15.   for (let i = nums.length - 1; i >= 0; i--) {
  16.     if (nums[i] < compare && lessLeft[i]) {
  17.       return true
  18.     }
  19.     compare = Math.max(compare, nums[i])
  20.   }
  22.   return false
  23. }