首页 > 剑指offer > 寻找下一个较大元素-面试题
2014
06-01

寻找下一个较大元素-面试题

这是一道亚马逊的面试题。给定一个数组,打印出每一个元素的下一个更大的元素( Next Greater Element,NGE ),就叫做NGE问题吧。

一个元素x的下一个更大的元素是指在x的右边第一个比该元素大的元素。如果没有更大的元素,则输出-1。
例如:

a) 任何数组,最右边的元素的NGE为-1。
b) 对于一个降序排序的数组,所有元素得到NGE为-1
c) 对于数组{4, 5, 2, 25}, NGE分别为 5,25,25,-1
d) 对于数组{13, 7, 6, 12}, NGE分别为 -1,12,12,-1

方法1 枚举

使用二重循环,分别遍历所有的元素,即可找到该元素的NGE。是否复杂度O(n^2).

方法2 使用栈

我们可以用栈来维护一个递减的序列,里面存储的数组左边未找到NGE的元素,初始时只包含第一个元素。我们可以假定栈顶就是最小的元素,因此可以用从栈顶top开始和后面的元素next比较。如果top<next则说明,找到了top的NGE,可以弹出栈。然后继续比较栈顶元素top和next,直到栈为空或 next <= top。然后把next加入栈,以便查找next的NGE。由于只有一次遍历,时间复杂度为O(n)

#include <iostream>
#include <stdio.h>
#include <stack>
using namespace std;

void findNGE(int arr[], int len){
	stack<int> s;
	s.push(arr[0]);
	int i=1;
	int top,next;
	for( i=1; i<len; i++){
		next = arr[i];
		top = s.top();

		//判断是否找到栈顶元素的NGE
		while(s.size() > 0 && top < next){
			 printf("\n %d --> %d", top, next);
			 s.pop(); //找到后 弹出

			 //继续判断栈顶
			 if(s.size() > 0)
				 top = s.top();
		}
		//将下一个元素入栈,以便查找其NGE
		s.push(next);
	}
	while(s.size() > 0){
		top = s.top();
		s.pop();
		printf("\n %d --> %d", top, -1);
	}
}

int main() {
	int arr[]= {11, 13, 10, 5, 12,21, 3};
	    int n = sizeof(arr)/sizeof(arr[0]);
	    findNGE(arr, n);
	return 0;
}

参考:http://www.geeksforgeeks.org/next-greater-element/


  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  2. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3

  3. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience

  4. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。