Mono-descreasing stack⌗

Key:

  1. The largest number is the root, that we can observe in by iteration.
  2. We must clear the stack to fill the right side of BST after loop.
  3. The last popped element is the left of current node. From top to bottom, the top element is the right side of the element that under the top.
class Solution {
public:
	TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
		vector<TreeNode*> res(nums.size(), nullptr);
		stack<int> st; // mono-descreasing stack, remove smaller elements before pushing.
		TreeNode* root = nullptr;
		for (int i = 0;i < nums.size(); i++) {
			res[i] = new TreeNode(nums[i]);

			while (!st.empty() && nums[st.top()] < nums[i]) {
				int j = st.top();
				st.pop();
				if (!st.empty() && nums[st.top()] < nums[i]) {
					res[st.top()]->right = res[j];
				} else {
					res[i]->left = res[j];
				}
			}

			if (root == nullptr || res[i]->val > root->val) {
				root = res[i];
			}
			st.push(i);
		}

		while (st.size() > 1) {
			int j = st.top();
			st.pop();
			res[st.top()]->right = res[j];
		}
		return root;
	}
};