在C ++中添加，删除和返回最大值和最小值之差的查询

在这个问题上，我们得到了Q个查询。这些是三种类型，它们是-

• 查询1：将数字N添加到列表中。

• 查询2：将数字N删除到列表中。

• 查询3：返回列表中最小和最大元素的差。

我们的任务是创建一个程序来解决要添加，删除和返回C ++中的最大值和最小值之差的查询。

问题描述

我们将获得要在列表上执行的Q个查询。有3种类型的查询可添加，删除和查找列表的最大和最小元素之间的差异。使用它，我们将首先构造元素列表，然后找到该列表的最大元素和最小元素之间的差异的查询3值。

让我们举个例子来了解这个问题，

输入：Q = 6

查询(1,4)

查询(1,9)

查询(1,6)

查询(2,4)

查询(1,3)

查询(3)

输出6

说明

最后，列表将为{9，6，3}。

最高-> 9

最低-> 3

差异-> 6

解决方法

解决问题的一种简单方法是直接解决每个查询。通过遵循这些步骤-

• 初始化数组。

• 对于查询类型1，将元素添加到数组中

• 对于查询类型2，从数组中删除一个元素

• 对于查询类型3，找到最大值和最小值之间的差，然后返回值。

示例

#include <iostream>
using namespace std;
void solveQuerry(int type, int item){
   int list[100];
   static int index = 0;
   if(type == 1){
      list[index] = item;
      index++;
   }
   else if(type == 2){
      for(int i = 0; i <= index; i++)
      if(list[i] == item ){
         list[i] = 0;
         break;
         }
      }
      else if(type == 3){
         int max = -100, min = 100;
      for(int i = 0; i< index; i++){
         if(list[i] == 0)
            i++;
         if(list[i] > max)
            max = list[i];
         if(list[i] < min)
            min = list[i];
      }
   cout<<"The difference between the maximum and minimum elements of the list is "<<(max - min);
   }
}
int main() {
   int Q = 6;
   int query[Q][2] = {{1, 5}, {1, 9}, {1, 6}, {2, 4}, {1, 3}, {3, 0}};
   for(int i = 0; i< Q; i++){
      solveQuerry(query[i][0], query[i][1]);
   }
}

输出结果

The difference between the maximum and minimum elements of the list is 6

如果我们使用其他数据结构而不是简单数组，则搜索过程会更有效。在这里，如果我们使用自平衡二进制搜索树而不是数组。max元素将位于末尾（使用rbegin()方法访问）。min元素将位于开头（使用begin()方法访问）。

使用该集完成了C ++中自平衡二进制搜索树的实现。

示例

#include <bits/stdc++.h>
using namespace std;
set<int> myList;
void solveQuerry(int type, int num){
   if(type == 1){
      myList.insert(num);
   }
   else if(type == 2){
      myList.erase(num);
   }
   else if(type == 3){
      int max = *(myList.rbegin());
      int min = *(myList.begin());
      cout<<"The difference between the maximum and minimum elements of the list is "<<(max - min);
   }
}
int main() {
   int Q = 6;
   int query[Q][2] = {{1, 5}, {1, 9}, {1, 6}, {2, 4}, {1, 3}, {3, 0}};
   for(int i = 0; i< Q; i++){
      solveQuerry(query[i][0], query[i][1]);
   }
}

输出结果

The difference between the maximum and minimum elements of the list is 6