739. 每日温度
 
 请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：
 要想观测到更高的气温，至少需要等待的天数。
 如果气温在这之后都不会升高，请在该位置用 0 来代替。

 例如，
 给定一个列表   temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，
 你的输出应该   results      = [1,   1,  4,  2,  1,  1,  0,  0]。

 提示：
 气温 列表长度的范围是 [1, 30000]。
 每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/daily-temperatures
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        //创建一个results数组
        vector<int> results = vector<int>(T.size());
        
        //创建一个栈，来查找元素右边第一个大于该元素的值
        stack<int> idxStack;
        
        //
        for (int i = 0; i<T.size(); i++) {
            //栈非空，且T[栈顶] < T[i],那么T[i]就是右侧第一个大于T[栈顶]的元素
            while (!idxStack.empty() && T[idxStack.top()] < T[i]) {
                results[idxStack.top()] = i - idxStack.top();
                idxStack.pop();
            }
            idxStack.push(i);
        }
        return results;
    }
};

654. 最大二叉树
 
 给定一个不含重复元素的整数数组。
 
 一个以此数组构建的最大二叉树定义如下：
 二叉树的根是数组中的最大元素。
 左子树是通过数组中最大值左边部分构造出的最大二叉树。
 右子树是通过数组中最大值右边部分构造出的最大二叉树。
 通过给定的数组构建最大二叉树，并且输出这个树的根节点。

 
 示例 ：
 输入：[3,2,1,6,0,5]
 输出：返回下面这棵树的根节点：
       6
     /   \
    3     5
     \    /
      2  0
        \
         1

 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/maximum-binary-tree
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

//递归方式实现
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return getRootNode(nums, 0, (int)nums.size());
    }
    
    TreeNode* getRootNode(vector<int>&nums,int lIdx,int rIdx){
        
        //递归基
        if (lIdx == rIdx) return nullptr;
        
        //寻找最大idx
        int maxIdx = lIdx;
        for (int i = lIdx; i<rIdx; i++) {
            if (nums[i] > nums[maxIdx]) maxIdx = i;
        }
        
        //创建根节点
        TreeNode * rootNode = new TreeNode(nums[maxIdx]);
        rootNode->left = getRootNode(nums,lIdx,maxIdx);
        rootNode->right = getRootNode(nums, maxIdx+1, rIdx);
        
        return rootNode;
    }
};

题目变种：返回一个数组，
数组里面存着每个节点的父节点的索引（如果没有父节点，就存-1）

class Solution {
public:
    vector<int> constructMaximumBinaryTree(vector<int>& nums) {

        //创建一个数组存放父节点的索引，默认值-1
        vector<int> result(nums.size(),-1);

        vector<int> left(nums.size(),-1);
        vector<int> right(nums.size(),-1);

        //创建一个栈，来寻找
        //左侧第一个大于该元素的元素和
        //右侧第一个大于该元素的元素
        stack<int> idxStack;
        
        
        //寻找右侧、左侧第一个大于该元素的元素
        for (int i = 0; i<nums.size(); i++) {
            
            //栈非空 并且 nums[i] > nums[idxStack.top()] 弹出
            while (!idxStack.empty() && nums[i] > nums[idxStack.top()]) {
                right[idxStack.top()] = i;
                idxStack.pop();
            }
            
            //来到此处栈顶就是nums[i]左侧第一个大于nums[i]元素的索引
            if (!idxStack.empty()){
                left[i] = idxStack.top();
            }
            idxStack.push(i);
        }
        
       
        //
        for (int i = 0; i<left.size(); i++) {
            int lIdx = left[i];
            int lVal = INT_MAX;
            if (lIdx != -1 ) {
                lVal =  nums[lIdx];
            }
           
            int rIdx = right[i];
            int rVal = INT_MAX;
            if (rIdx != -1) {
                rVal = nums[rIdx];
            }

            if (lVal < rVal) {
                result[i] = lIdx;
            }else{
                result[i] = rIdx;
            }
        }

        return result;
    }
};