题干描述

算法描述

• 使用变量small和mid，分别初始化为最大整数值
• 遍历数组，设当前数值为nums[i]
  • 如果nums[i]<=small：则 s m a l l ← n u m s [ i ] small \leftarrow nums[i] small←nums[i]
  • 否则，如果 s m a l l ≤ n u m s [ i ] ≤ m i d small \leq nums[i] \leq mid small≤nums[i]≤mid,则 m i d ← n u m s [ i ] mid \leftarrow nums[i] mid←nums[i]
  • 再否则，即 m i d < n u m s [ i ] mid < nums[i] mid<nums[i]，返回真
• 当遍历完成后，如果还没找到则返回假

class Solution {
    public boolean increasingTriplet(int[] nums) {
       int mid = Integer.MAX_VALUE;
       int small = Integer.MAX_VALUE;
       for(int i  : nums)
       {
            if (i <= small)
            {
                small = i;
            }
            else if(i<=mid)
            {
                mid = i;
            }
            else return true;
       }
       return false;
    }
}

正确性证明

• 由于第一个分支的优先级最高，所以small一定是当前遍历到所有元素中的最小值
  • 只要某个 n u m s [ i ] nums[i] nums[i]被用于执行更新small值，是不可能被用作任何满足条件元组的最大值或中间值的
  • 但若存在满足条件的元组，一定存在以这些被更新的某个small为最小值，small总是为当前的最小值进而保证了结果不会遗漏
  • 但small并不一定总是指向最终返回结果元组中最小的那个值
• 一般情况下，假设 n u m s [ 1 ⋯ i ] nums[1 \cdots i] nums[1⋯i]都是非递增的,且 i i i是满足条件的最大值。这意味着 n u m s [ i ] < n u m s [ i + 1 ] nums[i] < nums[i + 1] nums[i]<nums[i+1]。当遍历到 n u m s [ i ] nums[i] nums[i]时刻，small就被更新为 n u m s [ i ] nums[i] nums[i]，而mid还完全未被更新一次。
• 当遍历到 n u m s [ i + 1 ] nums[i + 1] nums[i+1]时，mid被更新为 n u m s [ i + 1 ] nums[i + 1] nums[i+1]
• 此后，mid始终指向最终返回结果元组（如果存在的话）中中间的那个值，并且始终隐含更新mid前最后一次的那个small
  • 考察mid被更新的情况，有可能在small对应的下标大于mid更新时对应下标的情况下被更新
    • 这种更新是合理的。假设未更新前的mid与后面的某个值构成满足条件的元组，则当前的small,mid和那个后面的值也构成满足条件的元组。结论成立。
  • 当mid更新时的下标大于small的下标时，结论更加显然。
• 考察返回的结果遍历到的 n u m s [ j ] nums[j] nums[j]
  • 如果此时small值对应的下标是小于mid的，由于mid在之前被更新过，所以这个就是满足条件的结果
  • 如果此时small对应的下标是大于mid的，因为一旦后面有大于mid的值，由于mid是以大于更新mid前最后一次的那个small的情况下更新后的结果，此时那个small和这个mid，加上这个遍历到的数，就构成了满足条件的三元组返回。