1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public boolean increasingTriplet(int[] nums) {
        Stack<Integer> monoStack = new Stack<>();
        boolean[] hasSmaller = new boolean[nums.length];
        for (int i = 0; i < nums.length; i++) {
            while (!monoStack.isEmpty() && nums[monoStack.peek()] >= nums[i]) {
                monoStack.pop();
            }
            if (!monoStack.isEmpty()) {
                hasSmaller[i] = true;
            }
            monoStack.push(i);
        }
        int currSecondSmallest = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > currSecondSmallest) {
                return true;
            }
            if (hasSmaller[i] && nums[i] < currSecondSmallest) {
                currSecondSmallest = nums[i];
            }
        }
        return false;
    }
}

关键在于我们需要得知道某个数字的左侧是否有比它小的, 如果左侧有比它小的, 那就说明这个数字至少是第二小, 不可能是最小. 知道每个位置的左侧是否有比该位置小的数字后, 我们从左开始遍历, 我们用一个变量来记录在左侧有比自己小的数字的那些元素里面, 值最小的, 因为满足有比自己小的条件的数字里面, 自己越小, 后来越有可能碰到数字比自己大. 因此我们到达一个数字后, 先看自己是否比这个变量大, 如果是那就成了, 因为这个变量记录的数字左侧也有比它小的, 现在我们又比这个变量大, 那么满足题意; 如果没有, 那么就需要看自己是不是左侧有比自己小的并且自己的值比这个记录变量小. 如果这两个条件同时满足, 那么自己是更合适的人选, 那么把自己的值赋给这个变量. 这个变量在上面的名字就叫做secondSmallest. 这是大致的思路.

时间复杂度: O(n) 第一遍遍历, 每个元素最多push进一次和pop出一次. 第二次遍历每个数字access一次, 因此一共是O(n)
空间复杂度: O(n) 因为用了栈.

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

更好的一种解决方法. 也是一样的思路. 还是找某个数字的左侧是否有比自己小的. 如果某个数字比自己左侧最小的还小, 那么该数字肯定左侧没有比自己小的, 因此我们需要一个变量来告诉我们在某个位置左侧的最小值是谁于是上面的first记录的是到某个位置时, 该位置左侧最小的数字. 到了某个位置后, 首先我们看自己是否比first小或等于, 如果是, 那完蛋了, 左侧没有比自己小的数字, 那我们继续. 如果到头了也没有找到有数字它的左侧有比它小的数字, 那就说明这个数组没有三连, 返回false. 但如果到了某个位置真让我们找到了一个数字比first大, 那感情好, 这个数字就是潜在的三连里面的第二个成员, 第一个成员可以是first(当然也可以是别的, first仅仅记录的是最小值, 至于有没有比first大但比当前数字小的数字存在, 也许有, 也许没有), 我们把第二个成员记录到second中. 然后我们继续走, 如果下一个数字比first小, 那这个数字也完蛋, 我们更新完first就继续走. 如果比first大, 那么这个数字也可以是潜在三连的第二个成员. 此时我们看看如果比first大, 那比second也大嘛, 如果是的话, 我们就成了. 如果比second也大, 那么直接返回true, 否则和second组不成三连. 但别急, 此时的值如果比second小, 那此时的值更有可能遇到比它大的值. 毕竟它小一点, 于是我们更新second, 因为我们知道此时的值左侧一定有比它小的数, 以后如果我们遇到一个数字比second大, 直接就可以返回true. 这就是大概的思路.

有个问题就是if, else if里面的等号必须要. 为什么? 假设我们不要, 如果当前的数字比first小, 那就更新first, 如果等于first呢? 我们会进入if else, 那肯定小于second, 从而给second赋值成了和first一样的数字, 这是不对的. 因此等号是要带上的. 如果小于等于first, 更新first, 如果比first大但是小于等于second, 那么更新second, 如果比second还大返回true. 三种条件是互斥的.

first装的是目前遇到的最小值. second装的是可能构成三连的中间的数字中最小的. 如果到达某个数字, 该数字比first小, 那该数字无法成为三连中的中间数字, 如果比first大但是比second小, 那么该数字就是目前可以构成三连的中间数字最小的, 更新second, 如果比second大, 恭喜, 此时triplet就成了.

时间复杂度: O(n)
空间复杂度: O(1)