题目描述

有一个数组，请找出数组中每个元素的下一个比它大的元素。

要求：

给定一个int数组arr以及数组大小为n，请返回一个int数组,代表每个元素比它大的下一个元素，若不存在返回-1，原数组中的元素都为正整数。

测试样例：

输入：[11,13,10,5,12,21,3] 7
输出：[13,21,12,12,21,-1.-1]

思路：

使用栈，从后往前使用一个递减栈
原数组最右边的数据，下一个最大值肯定是-1，所以栈的初始值为-1.
从后往前遍历数组：
1.如果原数组当前元素大于栈顶元素，则继续向栈底查找，一直遍历到栈值为-1或者原数组当前元素小于栈顶元素，这个栈顶元素就是要找的比本元素大的下一个元素。
2.如果原数组当前元素小于栈顶元素，栈顶元素就是要找的比本元素大的下一个元素。
3.将当前元素入栈。

代码实现

#include <stdio.h>
#include <stdlib.h>
int *next_great_data(int *arr,int n)
{int *result = (int *)malloc(n*sizeof(int));int top=-1;int stack[n];for(int i=n-1;i>=0;i--){while(top != -1 && arr[i] >= stack[top]){top--;}if(top == -1){result[i] = -1;}else{result[i] = stack[top];}stack[++top] = arr[i];}return result;
}int main()
{int array[]={2,118,9,5,12,21,7};int n = sizeof(array)/sizeof(array[0]);int *result =next_great_data(array,n);for(int i=0;i<n;i++){printf("%d ",result[i]);}printf("\n");free(result);return 0;
}

注：C++可以考虑用现有vector和stack容器实现