LeetCodeDay40 —— 递增的三元子序列★★☆

334. 递增的三元子序列

描述

• 给定一个未排序的数组，请判断这个数组中是否存在长度为3的递增的子序列。

示例

正式的数学表达如下:
  如果存在这样的 i, j, k,  且满足 0 ≤ i < j < k ≤ n-1，
  使得 arr[i] < arr[j] < arr[k] ，返回 true ; 否则返回 false 。
  要求算法时间复杂度为O(n)，空间复杂度为O(1) 。

  输入 [1, 2, 3, 4, 5],
  输出 true.

  输入 [5, 4, 3, 2, 1],
  输出 false.

思路

1. 找出中间的数，如果一个数左边存在比它大的，右边存在比它小的，则整个数组存在一个递增的三元序列。

1) 所以通过预处理的方法，第一遍遍历从左到右，记录每个数是否存在左边比其小的数
2) 第二遍遍历从右到左，判断是否有存在右边比其大的数，两者均满足则返回true
3) 算法时间复杂度为O(n)，空间复杂度为O(n)

2. 进一步优化预处理的方法，当遍历到第i个数时，有两种可能(参考)

1) 只找到一个最小数first，其为i-1个数中最小的
  a[i] < first, 更新first即可
  a[i] > first, 更新second为a[i]
2) 找到一个最小的递增对first,second,其中以second为关键字
  a[i] < first, 更新first, 此时需要记录新的first, 因为有可能存在更小的递增对
  a[i] > first and a[i] <= second，更新second为a[i]
  a[i] > second 返回true

class Solution_334_01 {
 public:
  bool increasingTriplet(vector<int>& nums) {
    int n = nums.size();
    if (n < 3) return false;
    vector<bool> hasSmaller(n, false);
    int smallest = nums[0];
    for (int i = 1; i < n; ++i) {
      if (nums[i] > smallest) hasSmaller[i] = true;
      if (nums[i] < smallest) smallest = nums[i];
    }
    vector<bool> hasbigger(n, false);
    int biggest = nums[n - 1];
    for (int i = n - 2; i >= 0; --i) {
      if (hasSmaller[i]) {
        if (nums[i] < biggest) return true;
      }
      if (nums[i] > biggest) biggest = nums[i];
    }
    return false;
  }
};

class Solution_334_02 {
 public:
  bool increasingTriplet(vector<int>& nums) {
    int n = nums.size();
    if (n < 3) return false;
    int first = INT_MAX, second = INT_MAX;
    for (int i = 0; i < n; ++i) {
      if (nums[i] < first) {
        first = nums[i];
      } else if (first < nums[i] && nums[i] <= second) {
        second = nums[i];
      } else if (nums[i] > second) {
        return true;
      }
    }
    return false;
  }
};