This solution is inspired by @votrubac

Here is his brilliant solution

https://discuss.leetcode.com/topic/98454/c-9-lines-o-n-log-n-map

The key idea is:

- We scan numbers from left to right, build the tree one node by one step;
- We use a stack to keep some (not all) tree nodes and ensure a decreasing order;
- For each number, we keep pop the stack until empty or a bigger number; The bigger number (if exist, it will be still in stack) is current number's root, and the last popped number (if exist) is current number's right child (temporarily, this relationship may change in the future); Then we push current number into the stack.

```
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
vector<TreeNode*> stk;
for (int i = 0; i < nums.size(); ++i)
{
TreeNode* cur = new TreeNode(nums[i]);
while (!stk.empty() && stk.back()->val < nums[i])
{
cur->left = stk.back();
stk.pop_back();
}
if (!stk.empty())
stk.back()->right = cur;
stk.push_back(cur);
}
return stk.front();
}
};
```

This solution will be slightly faster than normal recursive solution.

Again, great thanks to @votrubac !!!