找到数组右侧最远的较小数字的索引

Question

给定一个大小为 N 的数组。对于数组中的每个元素，任务是找到数组中最右边小于当前元素的元素的索引。如果不存在这样的数字，则打印 -1

本题摘自here

示例测试用例

Input 
3, 1, 5, 2, 4
Output
3, -1, 4, -1, -1

Input
1, 2, 3, 4, 0
Output 
4, 4, 4, 4, -1

我还想澄清一下，这不是此 post 的副本。虽然我确实理解 post 中提到的解决方案，但我真的很想知道为什么上述方法不适用于所有测试用例。

我想出了以下方法，

从数组右侧创建一个二叉搜索树
每个节点存储以下信息-值，当前元素的索引和离它右边最远的最小元素的索引
插入时，检查当前插入的元素（移动到右子树时）是否满足条件并相应地更新farthestDst

我试图提交这个，但我得到了错误的答案（未显示失败的测试用例）尽管运行成功地针对一些示例测试用例。我在下面附上了我的 C++ 代码

class TreeNode{
public:
    // farthestDst is the index of the smallest element which is farthest away from it's right side
    int val,idx,farthestDst;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int value, int index, int dst){
        val = value;
        idx = index;
        farthestDst = dst;
        left = right = NULL; 
    }
};

class Solution{   
  public:
    TreeNode* root = NULL;
    unordered_map <int,TreeNode*> mp; // store address of each node just to speed up search
    TreeNode* insertBST(TreeNode* root, int val, int idx, int dst){
        if(root == NULL){
            TreeNode* node = new TreeNode(val,idx,dst);
            mp[val] = node;
            return node;
        }
        else if(val >= root->val){ // checking the condition
            if((root->idx)-idx > dst){
                dst = root->idx;
            }
            root->right = insertBST(root->right,val,idx,dst);
        }
        else{
            root->left = insertBST(root->left,val,idx,dst);
        }
        return root;
    }
    // actual function to complete where N is the size of the vector and nums contains the values
    vector<int> farNumber(int N,vector<int> nums){
        vector<int> res;
        if(nums.size() == 0){ // base case check if nums is empty
            return res;
        }
        for(int i = nums.size()-1; i >= 0; i--){
            root = insertBST(root,nums[i],i,-1);
        }
        for(int i = 0; i < nums.size(); i++){
            TreeNode* node = mp[nums[i]]; 
            res.push_back(node->farthestDst);
        }
        return res;
    }
};

请注意，如果有人想测试他们的解决方案，他们可以在此 link

如果需要进一步说明代码，请告诉我

如有任何帮助，我们将不胜感激。谢谢！

Answer 1

mp[] 假定每个元素值在输入中最多出现一次。这不是作为问题描述的一部分给出的，因此不能保证。如果某个值出现不止一次，它在 mp[] 中的原始值将被覆盖。（具有讽刺意味的是，大多数 C++ 标准库将 unordered_map<T> 实现为 balanced BST —— AVL 树或 red-black 树。）

从技术上讲这不是错误，但正如 nice_dev 在评论中指出的那样，因为您的 BST 没有执行重新平衡，它可能会任意地变得很差，导致 O(n) 的插入时间为 O(n ^2) 整体表现。这将发生在例如已排序或 reverse-sorted 输入上。可能有大到足以导致 O(n^2) 时间算法超时的测试用例。

不幸的是，在您的代码中添加重新平衡以将 worst-case 时间降低到 O(n log n) 将导致它变得不正确，因为它目前依赖于一个微妙的属性：它不会将每个插入的元素与其右侧的 all smaller-valued 元素进行比较，而只会与您在从 BST 根向下的路径上遇到的元素进行比较。在此遍历期间，每当您在位置 j 处遇到值为 nums[j] < nums[i] 的元素时，您将忽略其左子树中的所有元素。对于您当前的实现，这是安全的：尽管 BST 属性已知这些元素都小于 nums[i]，但它们不能比 j 更靠右，因为插入顺序意味着每个 child 都在其 parent 的左侧。但是，如果您更改算法以执行树旋转以重新平衡树，则第二个属性可能会丢失 - 您可能会错过位置 k 的某些元素 nums[k] < nums[j] < nums[i] 但 k > j.

最后，同时拥有成员变量 root 和函数参数 root 令人困惑。

找到数组右侧最远的较小数字的索引

Find the index of the farthest smaller number in the right side of an array

arrays

algorithm

data-structures

binary-search-tree

binary-search