Compter le max d'éléments basé sur les opérations de pile C ++

Il existe plusieurs bugs dans votre code: trois bugs d'indexation et un bogue de transaction de mémoire. Tout d'abord, l'indexation de tableau C ++ commence toujours à partir de 0. Un premier premier index valide de N-Element Array est 0 et le dernier index valide est N-1.

1) due à ces raisons pour lesquelles la première boucle devrait être comme ceci: p> xxx pré>

2) élément inférieur, que vous appelez "max", doit être initialisé comme ceci: p> xxx pré>

3) Même observation sur la deuxième boucle: p>

delete[] arr;

Tout d'abord, vous devez obtenir l'exigence directement dans votre tête:

Vous avez une pile de n entiers. Dans une opération, vous pouvez apparaître un élément de la pile ou poussez n'importe quel élément éclabpé dans la pile. Vous devez maximiser l'élément supérieur de la pile après avoir effectué exactement K Opérations. Si la pile devient vide après avoir effectué des opérations K et qu'il n'y a pas d'autre moyen pour que la pile soit non vide, imprimez -1. P> blockQuote>

• donc, si n est 0, vous imprimez -1, sinon ... li>
• Si k est 0, vous imprimez haut (), sinon ... li>
• Si k est 1, vous devez faire pop () parce que vous n'avez rien à pousser, alors si N était vide que votre pile est vide et que vous devez imprimer -1, sinon imprimer haut (): quel que soit votre élément de 2e top arrivé; Sinon ... li>
• si x
• Si x == n, note que signifie que vous n'aurez toujours pas sauté la valeur finale de la pile, donc si c'est le plus grand élément que vous avez mal de chance: vous devrez pousser le 2e plus grand retour sur le dessus de la pile Sinon ... li> ul> li>
• Si x> n, vous pouvez apparaître tous les éléments, gaspiller toutes les opérations jusqu'à ce que vous ne receviez que 1 opération à gauche (en appuyant alternativement l'une des valeurs non plus importantes à l'époque si vous avez un autre op de gaspiller off), puis utilisez le dernier op pour repousser la plus grande valeur sur la pile; C'est équivalent em> pour trouver la plus grande valeur de la pile li> ul>

  Ainsi, le code qui trouve toujours le plus petit élément du top "X" Les éléments de pile ne modifient pas les opérations de pile que vous êtes supposés être disponibles. P>

  maintenant, juste parce que Vous comprenez quelle valeur votre programme de retour ne devrait pas dire que vous ne devez pas modéliser les opérations avec précision. Cela me semble que vous devez utiliser une pile, une poussée, des opérations POP et Top, et gardez une trace des valeurs que vous avez sautées afin que vous puissiez les repousser si nécessaire, et vous devrez peut-être pouvoir trouver le plus grand que vous '. J'ai sauté pour le remettre spécifiquement. P>

  faire tout cela, il est plus facile d'utiliser le std :: pile code> structure de données, et dites std :: multiiset code> pour stocker les éléments éclabètes dans la commande triée (vous pouvez donc trouver le plus grand facile). P>

  code ressemble à ceci . Il peut être rendu plus efficace / plus court, mais je vous laisserai cela. P>

  #include <iostream>
  #include <set>
  #include <stack>
  
  #define ASSERT(WHAT, MSG) \
      do { \
          if (!(WHAT)) { \
              std::cerr << "ASSERTION FAILURE AT LINE " \
                  << __LINE__ << ": " #WHAT "\n" << MSG << '\n'; \
          } \
      } while (false)
  
  #define DBG(MSG) std::cout << "DBG :" << __LINE__ << " " << MSG << '\n'
  
  // helper functions to be able to stream out containers we're using...
  std::ostream& operator<<(std::ostream& os, const std::multiset<int>& s)
  {
      os << "{ ";
      for (const auto& x : s) std::cout << x << ' ';
      return os << '}';
  }
  
  // note this makes a deep copy of the stack (because "s" is passed by value
  // not by reference), so we can pop all the elements destructively
  std::ostream& operator<<(std::ostream& os, std::stack<int> s)
  {
      os << "{ ";
      while (!s.empty())
      {
          std::cout << s.top() << ' ';
          s.pop();
      }
      return os << '}';
  }
  
  int main()
  {
      std::stack<int> s;
      std::multiset<int> popped;
  
      int n, k;
  
      ASSERT(std::cin >> n >> k, "input must have parseable int values for n and k");
  
      DBG("n " << n << ", k " << k);
      ASSERT(n >= 0, "n must not be negative");
      ASSERT(k >= 0, "k must not be negative");
  
      for (int i = 0; i < n; ++i)
      {
          int x;
          ASSERT(std::cin >> x, "input must have parseable int for value #" << i + 1);
          s.push(x);
      }
  
      DBG("initial stack " << s);
  
      if (n == 0)
          std::cout << -1 << '\n';
      else if (k == 0)
          std::cout << s.top() << '\n';
      else if (k == 1)
      {
          if (n == 1)
              std::cout << -1 << '\n';
          else
          {
              s.pop(); // have to use up our k1 operation as a pop
              std::cout << s.top() << '\n';
          }
      }
      else if (k <= n) // can't pop all the values
      {
          for (int i = 1; i < k; ++i)
          {
              DBG("popping " << s.top());
              popped.insert(s.top()); // add to popped...
              s.pop(); // ...and remove from stack
          }
          DBG("popped k-1 elements (sorted) " << popped);
          DBG("stack " << s);
          // use the last operation to put the largest popped value back
          // (if the stack's has size 2 or more, could pop another one instead -
          //  no way to know which is better, but if the values are random then
          //  the max of all the popped elements is likely to be more than any
          //  given element)
          s.push(*popped.rbegin());  // largest value seen...
          std::cout << s.top() << '\n';
      }
      else // k > n so can pop all the values...
      {
          DBG("k > n");
          while (!s.empty())
          {
              popped.insert(s.top());
              s.pop();
          }
          // waste however many spare operations we have...
          for (int i = 0; i < k - n - 1; ++i)
              if (i % 2 == 0) // on first, third, fifth iteration...
              {
                  DBG("push " << *popped.begin());
                  s.push(*popped.begin());  // push lowest value seen back to stack...
                  popped.erase(popped.begin());  // ...remove it from popped multiset
              }
              else
              {
                  DBG("pop " << s.top());
                  popped.insert(s.top());
                  s.pop();
              }
          DBG("popped elements (sorted) " << popped);
          DBG("stack " << s);
          s.push(*popped.rbegin());  // push largest value...
          std::cout << s.top() << '\n';
      }
  }