发表于 | 分类于

Given an array of characters, compress it in-place.

The length after compression must always be smaller than or equal to the original array.

Every element of the array should be a character (not int) of length 1.

After you are done modifying the input array in-place, return the new length of the array.

Follow up:

1
Could you solve it using only O(1) extra space?

Example 1:

1
2
3
4
5
6
7
8
Input:
["a","a","b","b","c","c","c"]
Output:
Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]
Explanation:
"aa" is replaced by "a2". "bb" is replaced by "b2". "ccc" is replaced by "c3".

Example 2:

1
2
3
4
5
6
7
8
Input:
["a"]
Output:
Return 1, and the first 1 characters of the input array should be: ["a"]
Explanation:
Nothing is replaced.

Example 3:

1
2
3
4
5
6
7
8
9
Input:
["a","b","b","b","b","b","b","b","b","b","b","b","b"]
Output:
Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].
Explanation:
Since the character "a" does not repeat, it is not compressed. "bbbbbbbbbbbb" is replaced by "b12".
Notice each digit has it's own entry in the array.

Note:
All characters have an ASCII value in [35, 126].
1 <= len(chars) <= 1000.

解法1： in-place

inplace的解法就是用一个pos记录当前需要插入的位置。
用一个变量last记录上一个字符，用count记录那个字符重复的次数。
如果当前字符和last一样则更新count，否则的话就写入到array中。

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    public int compress(char[] chars) {
        if (chars == null || chars.length == 0) {
            return 0;
        }
        if (chars.length == 1) return 1;
        int pos = 0;
        char last = chars[0];
        int count = 1;
        for (int i = 1; i < chars.length; i++) {
            char current = chars[i];
            if (current == last) {
                count++;
            } else {
                chars[pos++] = last;
                if (count > 1) {
                    String digit = Integer.toString(count);
                    for (char d : digit.toCharArray()) {
                        chars[pos++] = d;
                    }
                }
                count = 1;
                last = current;
            }
        }
        chars[pos++] = chars[chars.length - 1];
        if (count > 1) {
            String digit = Integer.toString(count);
            for (char d : digit.toCharArray()) {
                chars[pos++] = d;
            }
        }
        return pos;
    }
}

发表于 | 分类于

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

1

/ \
2 3
/ \
4 5
as “[1,2,3,null,null,4,5]”, just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

解法1： Preorder + Queue

先用Preorder构造serialization，在deserialize的时候用一个queue存放所有的node的string。
如果是“#”那么直接返回null，否则就知道当前的是一个node，然后分别递归剩下的，得到root.left和root.right的值。

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        List<String> temp = new ArrayList<>();
        helper(root, temp);
        // join them using ,
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < temp.size() - 1; i++) {
            sb.append(temp.get(i) + ",");
        }
        sb.append(temp.get(temp.size() - 1));
        return sb.toString();
    }
    private void helper(TreeNode root, List<String> sb) {
        if (root == null) {
            sb.add("#");
            return;
        }
        sb.add(Integer.toString(root.val));
        helper(root.left, sb);
        helper(root.right, sb);
    }
    // [1,2,#,#,3,4,#,#,5,#,#]
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.length() == 0) {
            return null;
        }    
        String[] comp = data.split(",");
        Queue<String> queue = new LinkedList<>();
        for (String c : comp) {
            queue.offer(c);
        }
        return deserialize(queue);
    }
    private TreeNode deserialize(Queue<String> queue) {
        if (queue.isEmpty()) {
            return null;
        }
        String rootVal = queue.poll();
        if (rootVal.equals("#")) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(rootVal));
        root.left = deserialize(queue);
        root.right = deserialize(queue);
        return root;        
    }
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

发表于 | 分类于

Given an integer n, return 1 - n in lexicographical order.

For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].

Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000.

解法1： DFS

观察规律的话，其实是从每一个数字往下画一个树。对于X，下面的数字就是x*10 + i, i从0到9为止。
而X的范围是1到9。
这样的话就很容易写出来DFS的程序了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> res = new ArrayList<>();
        for (int i = 1; i < 10; i++) {
            helper(res, i, n);
        }
        return res;
    }
    private void helper(List<Integer> res, int current, int n) {
        if (current > n) {
            return;
        } else {
            res.add(current);
            for (int i = 0; i < 10; i++) {
                if (current * 10 + i > n) {
                    return;
                }
                helper(res, current * 10 + i, n);
            }
        }
    }
}

解法2： Ietration

也有iteration的做法，这个方法的核心就是对于每一个数字，要找出对应的下一个数字。
第二个和第三个if语句里面解决的是对于499下一个数字的问题，应该是5而不是500，所以这种情况下要把末尾的9去掉，然后再把结果+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> res = new ArrayList<>();
        int current = 1;
        for (int i = 1; i <= n; i++) {
            res.add(current);
            if (current * 10 <= n) {
                current *= 10;
            } else if (current % 10 != 9 && current + 1 <= n) {
                current++;
            } else {
                while ((current / 10) % 10 == 9) {
                    current /= 10;
                }
                current = current / 10 + 1;
            }
        }
        return res;
    }
}

发表于 | 分类于

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

1
2
Input: 123
Output:  321

Example 2:

1
2
Input: -123
Output: -321

Example 3:

1
2
Input: 120
Output: 21

Note:
Assume we are dealing with an environment which could only hold integers within the 32-bit signed integer range. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

解法1：

这里用到了其中一种判断是否overflow的办法，就是先存下变化之前的数，然后变化之后做相同的操作看看是否和原来的数字一致。如果不相等则说明这个操作overflow了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int reverse(int x) {
        int res = 0;
        while ( x != 0) {
            int newRes = res;
            int digit = x % 10;
            newRes = res * 10 + digit;
            if ((newRes - digit) / 10 != res) {
                // overflow
                return 0;
            }
            res = newRes;
            x /= 10;
        }
        return res;
    }
}

发表于 | 分类于

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

解法1： HashMap

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
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) {
            return head;
        }
        Map<RandomListNode, RandomListNode> map = new HashMap<>();
        RandomListNode oldHead = head;
        while (head != null) {
            RandomListNode copy = new RandomListNode(head.label);
            map.put(head, copy);
            head = head.next;
        }
        head = oldHead;
        while (head != null) {
            map.get(head).random = map.get(head.random);
            if (head.next != null) {
                map.get(head).next = map.get(head.next);
            }
            head = head.next;
        }
        return map.get(oldHead);
    }
}

发表于 | 分类于

You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.

Define a pair (u,v) which consists of one element from the first array and one element from the second array.

Find the k pairs (u1,v1),(u2,v2) …(uk,vk) with the smallest sums.

Example 1:

1
2
3
4
5
6
Given nums1 = [1,7,11], nums2 = [2,4,6],  k = 3
Return: [1,2],[1,4],[1,6]
The first 3 pairs are returned from the sequence:
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

Example 2:

1
2
3
4
5
6
Given nums1 = [1,1,2], nums2 = [1,2,3],  k = 2
Return: [1,1],[1,1]
The first 2 pairs are returned from the sequence:
[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

Example 3:

1
2
3
4
5
6
Given nums1 = [1,2], nums2 = [3],  k = 3
Return: [1,3],[2,3]
All possible pairs are returned from the sequence:
[1,3],[2,3]

解法1：

discussion中的解法。要用到sorted这个条件可以简化不少程序。
由于两个都是sorted，那么第一个array中任何一个数字和第二个数组搭配时，最小的和一定是和第二个数组的第一个元素的配搭。
这样我们可以先把这个组合加入heap中，每次poll出来的时候就把对应的第二个数组的配搭往上挪一个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<int[]> res = new ArrayList<>();
        PriorityQueue<int[]> queue = new PriorityQueue<int[]>((a,b) -> (a[0] + a[1] - b[0] - b[1]));
        if (nums1.length == 0 || nums2.length == 0 || k == 0) {
            return res;
        }
        for (int i = 0; i < nums1.length; i++) {
            queue.offer(new int[]{nums1[i], nums2[0], 0});
        }
        while (k-- > 0 && !queue.isEmpty()) {
            int[] cur = queue.poll();
            res.add(new int[]{cur[0], cur[1]});
            int ptr = cur[2];
            if (ptr == nums2.length - 1) continue;
            queue.offer(new int[]{cur[0], nums2[ptr + 1], ptr + 1});
        }
        return res;
    }
}

发表于 | 分类于

You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.

If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.

Operations allowed:

Fill any of the jugs completely with water.
Empty any of the jugs.
Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.
Example 1: (From the famous “Die Hard” example)

1
2
Input: x = 3, y = 5, z = 4
Output: True

Example 2:

1
2
Input: x = 2, y = 6, z = 5
Output: False

解法1：

这里实际是一个数学定理，稍微看一下就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean canMeasureWater(int x, int y, int z) {
        if (x + y < z) return false;
        if (x == z || y == z || x + y == z) return true;
        return z % gcd(x, y) == 0;
    }
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

发表于 | 分类于

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user and is able to see the 10 most recent tweets in the user’s news feed. Your design should support the following methods:

postTweet(userId, tweetId): Compose a new tweet.
getNewsFeed(userId): Retrieve the 10 most recent tweet ids in the user’s news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
follow(followerId, followeeId): Follower follows a followee.
unfollow(followerId, followeeId): Follower unfollows a followee.
Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Twitter twitter = new Twitter();
// User 1 posts a new tweet (id = 5).
twitter.postTweet(1, 5);
// User 1's news feed should return a list with 1 tweet id -> [5].
twitter.getNewsFeed(1);
// User 1 follows user 2.
twitter.follow(1, 2);
// User 2 posts a new tweet (id = 6).
twitter.postTweet(2, 6);
// User 1's news feed should return a list with 2 tweet ids -> [6, 5].
// Tweet id 6 should precede tweet id 5 because it is posted after tweet id 5.
twitter.getNewsFeed(1);
// User 1 unfollows user 2.
twitter.unfollow(1, 2);
// User 1's news feed should return a list with 1 tweet id -> [5],
// since user 1 is no longer following user 2.
twitter.getNewsFeed(1);

解法1： Heap

用OOD设计的方法解这题比较清楚明白。在设计getNewsFeed的时候，用一个priorityQueue来把每一个follow的user的tweet的head放入堆中，按照时间顺序出堆入堆。每出一个就把当前指向的tweet的下一个推入堆中。

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
class Twitter {
    /** Initialize your data structure here. */
    class Tweet {
        int id;
        int time;
        Tweet next;
        public Tweet(int id) {
            this.id = id;
            this.time = timeStamp++;
            next = null;
        }
    };
    class User {
        int id;
        Set<Integer> followed;
        Tweet tweets;
        public User(int id) {
            this.id = id;
            followed = new HashSet<>();
            tweets = null;
            follow(id);
        }
        public void post(int tweetId) {
            Tweet tweet = new Tweet(tweetId);
            tweet.next = tweets;
            tweets = tweet;
        }
        public void follow(int id) {            
            if (!followed.contains(id)) {
                followed.add(id);
            }
        }
        public void unfollow(int id) {
            if (followed.contains(id)) {
                followed.remove(id);
            }
        }
    };
    int timeStamp = 0;    
    Map<Integer, User> userTable;
    public Twitter() {
        userTable = new HashMap<>();        
    }
    /** Compose a new tweet. */
    public void postTweet(int userId, int tweetId) {
        if (!userTable.containsKey(userId)) {
            userTable.put(userId, new User(userId));
        }
        User user = userTable.get(userId);
        user.post(tweetId);
    }
    /** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */
    public List<Integer> getNewsFeed(int userId) {
        List<Integer> res = new ArrayList<>();
        if (!userTable.containsKey(userId)) {
            return res;
        }
        User user = userTable.get(userId);
        Set<Integer> followed = user.followed;
        PriorityQueue<Tweet> queue = new PriorityQueue<>((a,b) -> b.time - a.time);
        for (Integer temp : followed) {
            User followed_user = userTable.get(temp);
            if (followed_user.tweets != null) {
                queue.offer(followed_user.tweets);
            }
        }
        int n = 0;
        while (!queue.isEmpty() && n < 10) {
            Tweet tweet = queue.poll();
            res.add(tweet.id);
            n++;
            if (tweet.next != null) {
                queue.offer(tweet.next);
            }
        }
        return res;
    }
    /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
    public void follow(int followerId, int followeeId) {
        if (!userTable.containsKey(followerId)) {
            userTable.put(followerId, new User(followerId));
        }
        if (!userTable.containsKey(followeeId)) {
            userTable.put(followeeId, new User(followeeId));
        }
        userTable.get(followerId).follow(followeeId);
    }
    /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
    public void unfollow(int followerId, int followeeId) {
        if (!userTable.containsKey(followerId) || followerId == followeeId) {
            return;
        }
        userTable.get(followerId).unfollow(followeeId);
    }
}
/**
 * Your Twitter object will be instantiated and called as such:
 * Twitter obj = new Twitter();
 * obj.postTweet(userId,tweetId);
 * List<Integer> param_2 = obj.getNewsFeed(userId);
 * obj.follow(followerId,followeeId);
 * obj.unfollow(followerId,followeeId);
 */

发表于 | 分类于

Design a Tic-tac-toe game that is played between two players on a n x n grid.

You may assume the following rules:

A move is guaranteed to be valid and is placed on an empty block.
Once a winning condition is reached, no more moves is allowed.
A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.
Example:
Given n = 3, assume that player 1 is “X” and player 2 is “O” in the board.

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
26
27
28
29
30
31
32
33
34
35
36
TicTacToe toe = new TicTacToe(3);
toe.move(0, 0, 1); -> Returns 0 (no one wins)
|X| | |
| | | |    // Player 1 makes a move at (0, 0).
| | | |
toe.move(0, 2, 2); -> Returns 0 (no one wins)
|X| |O|
| | | |    // Player 2 makes a move at (0, 2).
| | | |
toe.move(2, 2, 1); -> Returns 0 (no one wins)
|X| |O|
| | | |    // Player 1 makes a move at (2, 2).
| | |X|
toe.move(1, 1, 2); -> Returns 0 (no one wins)
|X| |O|
| |O| |    // Player 2 makes a move at (1, 1).
| | |X|
toe.move(2, 0, 1); -> Returns 0 (no one wins)
|X| |O|
| |O| |    // Player 1 makes a move at (2, 0).
|X| |X|
toe.move(1, 0, 2); -> Returns 0 (no one wins)
|X| |O|
|O|O| |    // Player 2 makes a move at (1, 0).
|X| |X|
toe.move(2, 1, 1); -> Returns 1 (player 1 wins)
|X| |O|
|O|O| |    // Player 1 makes a move at (2, 1).
|X|X|X|

Follow up:
Could you do better than O(n2) per move() operation?

解法1： O(N) move

基本的思路就是每次move之后，检查行，列，对角线是否满足胜利条件，如果满足就返回。

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
class TicTacToe {
    /** Initialize your data structure here. */
    int[][] board = null;
    int n;
    public TicTacToe(int n) {
        board = new int[n][n];        
        this.n = n;
    }
    /** Player {player} makes a move at ({row}, {col}).
        @param row The row of the board.
        @param col The column of the board.
        @param player The player, can be either 1 or 2.
        @return The current winning condition, can be either:
                0: No one wins.
                1: Player 1 wins.
                2: Player 2 wins. */
    public int move(int row, int col, int player) {
        board[row][col] = player;
        if (isWin(row, col, player)) return player;
        return 0;
    }
    private boolean isWin(int row, int col, int player) {
        // check row
        boolean win = true;
        for (int i = 0; i < n; i++) {
            if (board[row][i] != player) {
                win = false;
                break;
            }
        }
        if (win) return true;
        win = true;
        // check col
        for (int i = 0; i < n; i++) {
            if (board[i][col] != player) {
                win = false;
                break;
            }
        }
        if (win) return true;
        // check diagonal
        if (row == col) {
            win =  true;
            for (int i = 0; i < n; i++) {
                if (board[i][i] != player) {
                    win = false;
                    break;
                }
            }
        }
        if (win) return true;
        if (row + col == n - 1) {
            win = true;
            for (int i = 0; i < n; i++) {
                if (board[i][n - 1 - i] != player) {
                    win = false;
                    break;
                }
            }
        }
        if (win) return true;
        return false;
    }
}
/**
 * Your TicTacToe object will be instantiated and called as such:
 * TicTacToe obj = new TicTacToe(n);
 * int param_1 = obj.move(row,col,player);
 */

解法2： O(1) move

实际上这题可以做到o(1)的复杂度。用+1和-1表示每一个方向两个选手的落子情况。那么如果一个行都被其中一个选手占领，他的绝对值就一定和行数相等。由此

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class TicTacToe {
    private int[] rows;
    private int[] cols;
    private int diagonal;
    private int antiDiagonal;
    /** Initialize your data structure here. */
    public TicTacToe(int n) {
        rows = new int[n];
        cols = new int[n];
    }
    /** Player {player} makes a move at ({row}, {col}).
        @param row The row of the board.
        @param col The column of the board.
        @param player The player, can be either 1 or 2.
        @return The current winning condition, can be either:
                0: No one wins.
                1: Player 1 wins.
                2: Player 2 wins. */
    public int move(int row, int col, int player) {
        int toAdd = player == 1 ? 1 : -1;
        rows[row] += toAdd;
        cols[col] += toAdd;
        if (row == col)
        {
            diagonal += toAdd;
        }
        if (col == (cols.length - row - 1))
        {
            antiDiagonal += toAdd;
        }
        int size = rows.length;
        if (Math.abs(rows[row]) == size ||
            Math.abs(cols[col]) == size ||
            Math.abs(diagonal) == size  ||
            Math.abs(antiDiagonal) == size)
        {
            return player;
        }
        return 0;
    }
}
/**
 * Your TicTacToe object will be instantiated and called as such:
 * TicTacToe obj = new TicTacToe(n);
 * int param_1 = obj.move(row,col,player);
 */

发表于 | 分类于

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.
Your algorithm should run in O(n) time complexity and O(1) space complexity.

Examples:
Given [1, 2, 3, 4, 5],
return true.

Given [5, 4, 3, 2, 1],
return false.

解法1： O(N)

类似于一个贪心的算法，我们可以设两个变量，这两个变量的条件就是a < b,同时a，b要尽可能的小，这样在后续的扫描中如果发现有一个数字比a，b都大我们就找到了答案。

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