Diffculty: Medium

Input: [1,2,3,4,5]
Output: true

Input: [5,4,3,2,1]
Output: false

def increasingTriplet(nums: List[int]) -> bool:
    r1, r2 = sys.maxsize, sys.maxsize
    for n in nums :
        if n <= r1 : r1 = n
        elif n <= r2 : r2 = n
        else : return True
    return False
    
    # ============= 不同写法 ===============
    
    min_num,sec_num = float('inf'),float('inf')  # 初始化最小值，次小值
                                                     
    for i in nums:                               
        min_num = min(i,min_num)                 # 维护min_num为最小值
        if i > min_num:                          # 找到了次小值
            sec_num = min(i,sec_num)             
        if i > sec_num:                          # 找到了第三大的数
            return True

    return False

Input: [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, 
             the order of elements returned by next should be: [1,1,2,1,1].

Input: [1,[4,[6]]]
Output: [1,4,6]
Explanation: By calling next repeatedly until hasNext returns false, 
             the order of elements returned by next should be: [1,4,6].

# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger:
#    def isInteger(self) -> bool:
#        """
#        @return True if this NestedInteger holds a single integer, rather than a nested list.
#        """
#
#    def getInteger(self) -> int:
#        """
#        @return the single integer that this NestedInteger holds, if it holds a single integer
#        Return None if this NestedInteger holds a nested list
#        """
#
#    def getList(self) -> [NestedInteger]:
#        """
#        @return the nested list that this NestedInteger holds, if it holds a nested list
#        Return None if this NestedInteger holds a single integer
#        """

class NestedIterator:
    def __init__(nestedList: [NestedInteger]):
        ### 栈结构是从右到左, 但是遍历是从左到右, 所以需要反转再压栈
        self.stack = nestedList[::-1]
    
    def next(self) -> int:
        ### 由于hasNext()已经确保在栈顶的一定是integer, 所以可以直接出栈
        return self.stack.pop().getInteger()
    
    def hasNext(self) -> bool:
        ### 当栈的长度大于0和栈的下一个为List时, 就把该list添加到栈中 (同样需要反转才能入栈)
        while len(self.stack)>0 and not self.stack[-1].isInteger():
            self.stack += self.stack.pop().getList()[::-1]
        return len(self.stack) > 0  # 栈长度大于0说明有下一个


# Your NestedIterator object will be instantiated and called as such:
# i, v = NestedIterator(nestedList), []
# while i.hasNext(): v.append(i.next())

class NestedIterator(object):
    def __init__(self, nestedList):
        """
        Initialize your data structure here.
        :type nestedList: List[NestedInteger]
        """
        def build_generator(nestedList):
            for i in nestedList:
                if i.isInteger():
                    yield i.getInteger()
                else:
                    i = i.getList()
                    for j in build_generator(i):
                        yield j
        self.g = build_generator(nestedList)

    def next(self):
        """
        :rtype: int
        """
        #print(self.v)
        return self.v

    def hasNext(self):
        """
        :rtype: bool
        """
        try:
            self.v = next(self.g)
            #print(self.v)
            return True
        except:
            return False

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Input: nums = [1], k = 1
Output: [1]

def topKFrequent(nums: List[int], k: int) -> List[int]:
    import random 
    from collections import Counter

    lookup = Counter(nums)
    nums = [(freq, num) for num, freq in lookup.items()]
    random.seed(42)
    # 返回的是最大的前k个元组
    kths =  self.findKth(nums, k, 0, len(nums)-1)
    # print(kths)
    return [num for (freq, num) in kths]
    
# 找到第k大的数所在的位置，返回nums中k及其前面全部的元素；时间复杂度O(n)
def findKth(self, nums, k, low, high) :
    import random 
    if low >= high : return nums[:low+1]
    pivot = random.randint(low, high)
    nums[low], nums[pivot] = nums[pivot], nums[low]
    base = nums[low][0]
    i = low
    for j in range(low+1, high+1) :
        if nums[j][0] > base :
            nums[j], nums[i+1] = nums[i+1], nums[j]
            i += 1
    nums[low], nums[i] = nums[i], nums[low]
    if i == k-1 :
        return nums[:i+1]
    elif i > k - 1 :
        return self.findKth(nums, k, low, i-1)
    else :
        return self.findKth(nums, k, i+1, high)

def topKFrequent(nums: List[int], k: int) -> List[int]:
    from collections import Counter
    lookup = Counter(nums)
    # return [num for num, freq in lookup.most_common(k)]
    print(lookup) # Counter({1: 3, 2: 2, 3: 1})
    print(lookup.most_common(1)) # [(1, 3)]
    print(lookup.most_common(2)) # [(1, 3), (2, 2)]
    return [item[0] for item in lookup.most_common(k)]

def topKFrequent(nums: List[int], k: int) -> List[int]:
    from collections import Counter
    import heapq
    count = Counter(nums)   
    return heapq.nlargest(k, count.keys(), key=count.get)

Given n = 3, assume that player 1 is "X" and player 2 is "O" in the board.

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|

class TicTacToe(object):
    def __init__(self, n):
        """
        Initialize your data structure here.
        :type n: int
        """
        self.n = n
        self.rowMoveCount1 = [0] * n # maps k to how many pos in row k are occupied by player 1
        self.rowMoveCount2 = [0] * n # maps k to how many pos in row k are occupied by player 2
        self.colMoveCount1 = [0] * n # maps k to how many pos in col k are occupied by player 1
        self.colMoveCount2 = [0] * n # maps k to how many pos in col k are occupied by player 2
        self.mainDiagMoveCount1 = [0] # how many pos in main diag (row==col) are occupied by player 1
        self.mainDiagMoveCount2 = [0] # how many pos in main diag (row==col) are occupied by player 2
        self.antiDiagMoveCount1 = [0] # how many pos in anti diag (row+col==n-1) are occupied by player 1
        self.antiDiagMoveCount2 = [0] # how many pos in anti diag (row+col==n-1) are occupied by player 2

    def move(self, row, col, player):
        """
        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.
        :type row: int
        :type col: int
        :type player: int
        :rtype: int
        """
        assert player==1 or player==2

        rowCountList = self.rowMoveCount1 if player==1 else self.rowMoveCount2
        colCountList = self.colMoveCount1 if player==1 else self.colMoveCount2
        mainDiagCountList = self.mainDiagMoveCount1 if player==1 else self.mainDiagMoveCount2
        antiDiagCountList = self.antiDiagMoveCount1 if player==1 else self.antiDiagMoveCount2

        rowCountList[row] += 1
        colCountList[col] += 1
        if row == col:
            mainDiagCountList[0] += 1
        if row + col == self.n - 1:
            antiDiagCountList[0] += 1

        if self.n in [ rowCountList[row], colCountList[col], mainDiagCountList[0], antiDiagCountList[0] ]:
            return player
        else:
            return 0

# Your TicTacToe object will be instantiated and called as such:
# obj = TicTacToe(n)
# param_1 = obj.move(row,col,player)