题目描述
现在我们有一个int数组,请你找出数组中每个元素的下一个比它大的元素。
给定一个int数组A及数组的大小n,请返回一个int数组,代表每个元素比他大的下一个元素,若不存在则为-1。保证数组中元素均为正整数。
测试样例:
[11,13,10,5,12,21,3],7
返回:[13,21,12,12,21,-1,-1]
思路
从后向前维护一个递减栈。
最右边的那个值肯定没有最大值,所以肯定是-1。初始栈为-1。
从后向前计算:
(1)如果当前元素大于栈顶元素,则栈顶元素退出,如果还是大于栈顶元素,继续退出,一直遍历栈到-1或者小于栈顶元素。这个元素就是就是当前值的下一个比较大的元素。
(2)如果当前元素小于栈顶元素,栈顶元素就是当前值的下一个比较大的元素。
再简化一下代码如下
代码
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
class NextElement {
public:
vector<int> findNext(vector<int> A, int n) {
vector<int> result;
if(n <= 0){
return result;
}
stack<int> stack;
stack.push(-1);
for(int i = n-1;i >= 0;--i){
int top = stack.top();
while(top != -1 && A[i] >= top){
stack.pop();
top = stack.top();
}
result.insert(result.begin(),top);
stack.push(A[i]);
}
return result;
}
};
int main() {
NextElement s;
vector<int> vec = {7,12,5,8,11};
vector<int> result = s.findNext(vec,5);
for(int i = 0;i < result.size();++i){
cout<<result[i]<<" ";
}
cout<<endl;
return 0;
}
<script type="text/javascript">
$(function () {
$('pre.prettyprint code').each(function () {
var lines = $(this).text().split('\n').length;
var $numbering = $('<ul/>').addClass('pre-numbering').hide();
$(this).addClass('has-numbering').parent().append($numbering);
for (i = 1; i <= lines; i++) {
$numbering.append($('<li/>').text(i));
};
$numbering.fadeIn(1700);
});
});
</script>
分享到:
相关推荐
程序员面试金典 第5版.pdf.7z.001
程序员面试金典 第5版.pdf.7z.002
最全的程序员面试金典5,清晰易读,面试金典案例,包括java,c++等面试金典题型
资源名称:程序员面试金典-第五版资源截图: 资源太大,传百度网盘了,链接在附件中,有需要的同学自取。
JAVA程序员面试题集合.pdf JAVA程序员面试题集合.pdf
JAVA程序员面试32问.JAVA程序员面试32问.JAVA程序员面试32问.
软件介绍: 众多互联网公司如谷歌微软面试员工书籍,英文完整版,对需要参加面试的同学有一定的帮助价值,不过,本人表示完全看不懂。
java程序员面试葵花宝典.rar java程序员面试葵花宝典.rar java程序员面试葵花宝典.rar java程序员面试葵花宝典.rarjava程序员面试葵花宝典.rarjava程序员面试葵花宝典.rar
Java程序员面试陷阱大全.doc Java程序员面试陷阱大全.doc Java程序员面试陷阱大全.doc
程序员面试金典的完整代码,github上下载,仅供学术交流。
程序员面试金典 源码 包含JAVA、C、c++等语言实现
JAVA程序员面试32问.非常经典的java面试题库
程序员面试金典 第5版.part1.rar
程序员面试金典 第六版英文 Cracking the Coding Interview(6th)
程序员面试金典 第5版.part2.rar
JAVA程序员面试32问.doc JAVA程序员面试32问.doc
程序员面试试题.txt程序员面试试题.txt程序员面试试题.txt程序员面试试题.txt
程序员面试金典文字版-带目录(第5版),还是很不错的,积分比较少,大家可以随意下载,程序员面试金典是非常经典的,对面试来说也非常哟用,能明显提高面试技巧,确实还是很不错的
程序员面试介绍项目经验程序员面试介绍项目.pdf,这是一份不错的文件