需要找到数组中每个元素的下一个更大的元素。
需要找到数组中每个元素的下一个更大的元素。
提问于 2014-06-08 04:40:47
对算法的描述
对于输入数组中的每个元素，对应的输出是输入元素后面的第一个数字，比输入元素大。
换句话说，对于给定的输入，输出是一些元素inputj，其中j是最小索引，使得j>i和inputj > inputi。
示例
Input 12 15 22 9 7 2 18 23 27
Output 15 22 23 18 18 18 23 27 -1例如，与9对应的输出为18，因为18是数组中满足这些要求的第一个数字。
- 在输入数组中跟随9
- 大于9
问题
有人能给我推荐比O(n^2)更好的算法吗？
回答 2
Stack Overflow用户
发布于 2014-06-08 12:53:09
这可以通过两个堆栈(一个用于索引，另一个用于值)在O(N)时间和O(N)额外内存空间中完成。
我将用你的例子解释这个算法。
Input 12 15 22 9 7 2 18 23 27
Initialize Output Array O[] as all -1.
1. Start from the first element. Set CurrentElement = A[0] (12). index = 0
2. Push A[index] in a Stack S_values. Push index in a Stack S_indices.
3. Increment index.
4. while ( S_values is not empty && A[index] is > than S_values.top() )
- Set output_index = S_indices.top()
- set O[output_index] = A[index].
- S_values.pop()
- S_indices.pop().
5. If index < length(Input)-1 Goto Step 2.
6. Set O[index] = -1. // Last element.这是因为堆栈S_values的顶部始终具有最低的值，并且元素将按升序从其中弹出。类似地，堆栈S_indices在顶部总是有最大的值，索引将按降序出现。
编辑: C++中的代码
#include <vector>
#include <stack>
#include <iostream>
using std::cout;
using std::endl;
using std::vector;
using std::stack;
int main()
{
vector<int> Input = { 12, 15, 22, 9, 7, 2, 18, 23, 27};
vector<int> Output( Input.size(), -1 );
stack<int> S_values, S_indices;
S_values.push( Input[0] );
S_indices.push( 0 );
for ( size_t index = 1; index < Input.size(); ++index )
{
while ( !S_values.empty() && Input[index] > S_values.top() )
{
size_t output_index = S_indices.top();
Output[ output_index ] = Input[ index ];
S_values.pop();
S_indices.pop();
}
S_values.push( Input[index] );
S_indices.push( index );
}
for ( auto &x : Output )
cout << x << " ";
cout << endl;
return 0;
}输出：
15 22 23 18 18 18 23 27 -1Stack Overflow用户
发布于 2014-06-08 07:10:49
一种方法是使用堆栈，其中堆栈中的每个条目都是值:索引对。迭代输入数组，从堆栈中弹出值小于输入数组中当前项的值的项。一旦所有较小的值都从堆栈中弹出，将当前值:index对推到堆栈上。当到达输入数组的末尾时，堆栈中的任何剩余条目的输出值为-1，表明没有找到更大的数目。
使用问题中的示例，下面是算法的工作方式
input item 12
stack = 12:0
input item 15
pop 12:0 and set output[0] = 15
stack = 15:1
input item 22
pop 15:1 and set output[1] = 22
stack = 22:2
input item 9
stack = 9:3, 22:2
input item 7
stack = 7:4, 9:3, 22:2
input item 2
stack = 2:5, 7:4, 9:3, 22:2
input item 18
pop 2:5 and set output[5] = 18
pop 7:4 and set output[4] = 18
pop 9:3 and set output[3] = 18
stack = 18:6, 22:2
input item 23
pop 18:6 and set output[6] = 23
pop 22:2 and set output[2] = 23
stack = 23:7
input item 27
pop 23:7 set output[7]= 27
stack = 27:8
end of array
pop 27:8 and set output[8] = -1
done页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/24103061
复制相关文章
相似问题
腾讯云开发者
