讨论/《算法面试题汇总》 - 递增的三元子序列/
《算法面试题汇总》 - 递增的三元子序列
共 7 个回复

精妙绝伦的三种java解法,更多详细题解请移步github力扣算法视频题解,B站更有对应的题解视频呦。

class Solution {
    public boolean increasingTriplet1(int[] nums) {
        // 时间:O(N^2),空间:O(1)
        int N = nums.length;
        for (int i = 0; i < N; i++) {
            if (checkLeft(i, nums) && checkRight(i, nums)) return true;
        }
        return false;
    }

    private boolean checkLeft(int ind, int[] nums) {
        int i = ind - 1;
        while (i >= 0 && nums[i] >= nums[ind]) i--;
        if (i >= 0) return true;
        else return false;
    }
    private boolean checkRight(int ind, int[] nums) {
        int i = ind + 1, N = nums.length;
        while (i < N && nums[i] <= nums[ind]) i++;
        if (i < N) return true;
        else return false;
    }

    public boolean increasingTriplet2(int[] nums) {
        // 时间:O(3N) = O(N),空间:O(2N) = O(N)
        int N = nums.length;
        // left[i] 存储从[0, i]区间的最小值
        // right[i] 存储从[i, N - 1]区间的最大值
        int[] left = new int[N];
        int[] right = new int[N]; 
        left[0] = nums[0];
        right[N - 1] = nums[N - 1];
        for (int i = 1; i < N; i++) left[i] = Math.min(nums[i], left[i - 1]);
        for (int i = N - 2; i >= 0; i--) right[i] = Math.max(nums[i], right[i + 1]);
        for (int i = 1; i < N - 1; i++) {
            if (nums[i] > left[i - 1] && nums[i] < right[i + 1]) return true;
        }
        return false;
    }

    public boolean increasingTriplet(int[] nums) {
        // 时间:O(N), 空间O(1)
        int small = Integer.MAX_VALUE, mid = Integer.MAX_VALUE;
        for (int num: nums) {
            if (small >= num) small = num;
            // 进入到mid的语句块意味着 small < num <= mid;
            else if (mid >= num) mid = num;
            // 进入到return语句块意味着 num > mid, num > samll
            // 要注意small和mid初始值都是int的最大值,能进入到return语句块,意味着,此刻small和mid
            // 都已经发生过赋值了,一旦赋值过,肯定满足 mid > small,因此直接返回true即可。
            else return true;
        } 
        return false;
    }
}
1

维护两个变量a,b

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        res = [] #存储3个数a < b < c
        res.append(nums[0])
        for i in range(1,len(nums)):
            if len(res) == 1:
                if nums[i] <= res[0]:  #更新a
                    res[0] = nums[i]
                else:
                    res.append(nums[i]) #添加b 

            elif len(res) == 2:
                if nums[i] <= res[0]: #可以更新a,b不需要改动,此时已经完成匹配a<b
                    res[0] = nums[i]
                elif res[0] < nums[i] < res[1]:  #可以更新b
                    res[1] = nums[i] 
                elif nums[i] > res[1]:
                    res.append(nums[i])
                    return True 
            # print(res)
        return False         

这个没问题,此时b在nums索引是1,值为102,所以a只要比102小就行,输出结果是[2,1,3],因为取得是值最小的a,b,c。但是我可以取第二小的a,最下的b,最小的c,即[0,1,3]完成匹配。最后a会更新为索引2是防止后面b,c也会更新。

第三个有问题吧,虽然判断结果是对的,但是如果要输出序列的话就是错的了。[100,102,10,130,120],这个应该输出[0,1,3],而代码执行的话应该是[2,1,3]了

10 12 13

输入:
[20,100,10,12,5,13]
输出:
false
预期结果:
true

这条case是不是又问题呀,还是我理解题意理解的又问题

var increasingTriplet = function (nums) {
    let i = 0, min = nums[0], temp = Number.MAX_VALUE
    for (let i = 1; i < nums.length-1; i++) {
        min = Math.min(min, nums[i])
        if (nums[i] > min) {
            temp = nums[i]
        }
        if (temp < nums[i + 1]) {
            return true
        }
    }
    return false
};