-1

给你一堆 N 个整数。在一个操作中，您既可以从堆栈中弹出一个元素，也可以将任何弹出的元素压入堆栈。您需要在执行完 K 次操作后最大化堆栈的顶部元素。如果堆栈在执行 K 次操作后变空并且没有其他方法使堆栈不为空，则打印 -1。

我正在动态分配内存然后释放内存。我无法理解为什么我会面临这个问题。

#include "pch.h"
#include<iostream>
using namespace std;
int main()
{
int n, x, max;
cin >> n;
cin >> x;
int* arr = new int[n];
    //Storing the values from the last, since the first element represents 
    //top of the stack, so the first element would be latest element which 
    //will be pushed into the stack
for (int i = n; i > 0; i--)
{
    cin >> arr[i];
}
max = arr[n];
    //Finding the max by iterating from the last position to the no of 
    //stack operations performed.
for (int i = n; i >= x; i--)
{
    if (arr[i] > max)
    {
        max = arr[i];
    }
}
cout << max;
delete arr;
return 0;
}

输入 ：

6 4
1 2 4 3 3 5

预期输出：

4

错误：

Error Message : Debug Error ! Program :- Heap Corruption detected : after 
normal block c#2368 at 0x01d21e30. CRT detected that the application wrote 
memory after end of heap buffer.
4

3 回答 3

2

您的代码中有几个错误：三个索引错误和一个内存释放错误。首先，在 C++ 中，数组索引总是从 0 开始。所以 n 元素数组的第一个有效索引是 0，最后一个有效索引是 n-1。

1）由于这些原因，第一个循环应该是这样的：

for (int i = n-1; i >= 0; i--) { ... }

2）底部元素，你称之为'max'，应该像这样初始化：

max = arr[n-1];

3）关于第二个循环的相同观察：

for (int i = n-2; i >= x; i--) { ... }

4) 数组的重新分配应该使用操作符delete[]而不是delete. 否则，您将有内存泄漏和未定义的行为。在这里您可以找到有关这些运算符的一些附加信息：

delete[] arr;
于 2019-05-28T15:57:53.907 回答
1

在大小为n的数组中，有效索引是从 0 到n-1，而不是从 1 到n

警告当您使用new分配数组时，您必须使用delete []

我还鼓励您在读取值时检查读取是否成功，否则当前容器未设置并且所有下一次读取将什么也不做

例如从您的代码：

#include <iostream>

using namespace std;

int main()
{
  int n, x, max;

  if ((! (cin >> n)) || (n < 1))
    cerr << "invalid size" << endl;
  else if ((! (cin >> x)) || (x < 0) || (x >= n))
    cerr << "invalid min index" << endl;
  else {
    int* arr = new int[n];
    //Storing the values from the last, since the first element represents 
    //top of the stack, so the first element would be latest element which 
    //will be pushed into the stack
    for (int i = n-1; i >= 0; i--)
    {
      if (!(cin >> arr[i])) {
        cerr << "invalid value" << endl;
        return 0;
      }
    }
    max = arr[n-1];
    //Finding the max by iterating from the last position to the no of 
    //stack operations performed.
    for (int i = n-2; i >= x; i--)
    {
      if (arr[i] > max)
        {
          max = arr[i];
        }
    }
    cout << max << endl;
    delete arr; // must be delete [] arr;
  }
  return 0;
}

事实上，我检查了一个整数是否输入了我还检查了大小/最小索引是否严格为正，并检查了最小索引的有效性

循环查找与自身比较的最大值也是没有用的arr[n-1]，所以第一个考虑的索引是n-2

从最后一个索引填充数组似乎很奇怪

你使用一个数组，但你也可以使用一个vector<int>，std::vector非常实用

编译和执行：

pi@raspberrypi:/tmp $ g++ -pedantic -Wall -Wextra v.cc
pi@raspberrypi:/tmp $ ./a.out
aze
invalid size
pi@raspberrypi:/tmp $ ./a.out
-1
invalid size
pi@raspberrypi:/tmp $ ./a.out
3 qsd
invalid min index
pi@raspberrypi:/tmp $ ./a.out
3 4
invalid min index
pi@raspberrypi:/tmp $ ./a.out
6 4
1 2 4 3 3 5
2
pi@raspberrypi:/tmp $

请注意，由于索引的变化，结果是 2 而不是 4，如果您希望索引从 1 开始为用户做

#include<iostream>

using namespace std;

int main()
{
  int n, x, max;

  if ((! (cin >> n)) || (n < 1))
    cerr << "invalid size" << endl;
  else if ((! (cin >> x)) || (x < 1) || (x > n))
    cerr << "invalid min index" << endl;
  else {
    x -= 1;

    int * arr = new int[n];
    //Storing the values from the last, since the first element represents 
    //top of the stack, so the first element would be latest element which 
    //will be pushed into the stack
    for (int i = n-1; i >= 0; i--)
    {
      if (!(cin >> arr[i])) {
        cerr << "invalid value" << endl;
        return 0;
      }
    }
    max = arr[n-1];
    //Finding the max by iterating from the last position to the no of 
    //stack operations performed.
    for (int i = n-2; i >= x; i--)
    {
      if (arr[i] > max)
        {
          max = arr[i];
        }
    }
    cout << max << endl;
    delete arr; // must be delete [] arr;
  }
  return 0;
}

编译和执行：

pi@raspberrypi:/tmp $ g++ -pedantic -Wall -Wextra v.cc
pi@raspberrypi:/tmp $ ./a.out
6 4
1 2 4 3 3 5
4
pi@raspberrypi:/tmp $

在valgrind下执行表明错误free arr：

pi@raspberrypi:/tmp $ valgrind ./a.out
==3761== Memcheck, a memory error detector
==3761== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==3761== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==3761== Command: ./a.out
==3761== 
6 4
1 2 4 3 3 5
4
==3761== Mismatched free() / delete / delete []
==3761==    at 0x48491EC: operator delete(void*) (vg_replace_malloc.c:576)
==3761==    by 0x10BE7: main (in /tmp/a.out)
==3761==  Address 0x4bcb388 is 0 bytes inside a block of size 24 alloc'd
==3761==    at 0x48485F0: operator new[](unsigned int) (vg_replace_malloc.c:417)
==3761==    by 0x10A9F: main (in /tmp/a.out)
==3761== 
==3761== 
==3761== HEAP SUMMARY:
==3761==     in use at exit: 0 bytes in 0 blocks
==3761==   total heap usage: 4 allocs, 4 frees, 22,296 bytes allocated
==3761== 
==3761== All heap blocks were freed -- no leaks are possible
==3761== 
==3761== For counts of detected and suppressed errors, rerun with: -v
==3761== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 6 from 3)
pi@raspberrypi:/tmp $
于 2019-05-28T15:42:41.267 回答
0

首先，您需要直截了当地提出要求：

给你一堆 N 个整数。在一个操作中，您既可以从堆栈中弹出一个元素，也可以将任何弹出的元素压入堆栈。您需要在执行完 K 次操作后最大化堆栈的顶部元素。如果堆栈在执行 K 次操作后变空并且没有其他方法使堆栈不为空，则打印 -1。

  • 因此，如果 N 为 0，则打印 -1，否则...
  • 如果 K 为 0，则打印 top()，否则...
  • 如果 K 为 1，则必须 pop()，因为您没有要推送的内容，因此如果 N 为 1，则您的堆栈为空，您必须打印 -1，否则打印 top()：无论您的第二个顶部元素是什么; 除此以外...
  • 如果 x <= N，您可以弹出 x - 1 个元素，然后将其中最大的元素推回堆栈顶部
    • 如果 x == N，请注意这意味着您仍然不会从堆栈中弹出最终值，所以如果它是最大的元素，您就不走运了：您必须将第二大的元素推回顶部否则堆栈...
  • 如果 x > N，您可以弹出所有元素，浪费任何操作，直到您只剩下 1 个操作（通过交替推回任何一个非最大值，然后如果您有另一个操作浪费弹出它），然后使用最后一个操作将最大值推回堆栈；这相当于在堆栈中找到最大值

因此，始终在顶部“x”堆栈元素中找到最小元素的代码不会对您应该可用的堆栈操作进行建模。

现在，仅仅因为您了解您的程序应该返回什么值并不意味着您不应该准确地为操作建模。在我看来，您应该使用堆栈、推送、弹出和顶部操作，并跟踪您弹出的值，以便在必要时将它们推回，您可能需要能够找到最大的我突然特意把它放回去了。

为此，最简单的方法是使用std::stack数据结构，并按std::multiset排序顺序存储弹出的元素（这样您就可以轻松找到最大的元素）。

代码看起来像这样。它可以变得更高效/更短，但我会把它留给你。

#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';
    }
}
于 2019-05-28T17:12:16.870 回答