975. odd even step

tags

treemap, dynamic programming

Solution

definition

• dp[i][0] true - start from index i at odd step can success

• dp[i][1] true - start from index i at even step can success

• dp[i][0] = dp[i’s next greater number][1]

• dp[i][1] = dp[i’s next smaller number][0]

steps

• start from n - 2, reversely trace back and add elements into treemap

Complexity

• time: O(nlgn)
• space: O(n)