网站的风格有哪些,hm网上商城,做专业慢摇的网站,网站做ssl证书有风险题目
题目描述
这天小明买彩票中了百亿奖金#xff0c;兴奋的他决定买下蓝桥公司旁的一排连续的楼房。
已知这排楼房一共有 N 栋#xff0c;编号分别为 1∼N#xff0c;第 i 栋的高度为 hi。
好奇的小明想知道对于每栋楼#xff0c;左边第一个比它高的楼房是哪个兴奋的他决定买下蓝桥公司旁的一排连续的楼房。
已知这排楼房一共有 N 栋编号分别为 1∼N第 i 栋的高度为 hi。
好奇的小明想知道对于每栋楼左边第一个比它高的楼房是哪个右边第一个比它高的楼房是哪个若不存在则输出 −1−1。但由于楼房数量太多小明无法用肉眼直接得到答案于是他花了 11 个亿来请你帮他解决问题你不会拒绝的对吧
输入描述
第 11 行输入一个整数 N表示楼房的数量。
第 22 行输入 N 个整数相邻整数用空格隔开分别为 h1,h2,...,hN表示楼房的高度。
1≤N≤7×10^51≤hi≤10^9。
输出描述
输出共两行。
第一行输出 N 个整数表示每栋楼左边第一栋比自己高的楼的编号。
第二行输出 N 个整数表示每栋楼右边第一栋比自己高的楼的编号。
输入输出样例
示例 1
输入
5
3 1 2 5 4 输出
-1 1 1 -1 4
4 3 4 -1 -1运行限制
最大运行时间2s最大运行内存: 256M
提交代码
//百亿富翁//编号从1开始
//左侧第一个比自己高的楼房的编号
//右侧第一个比自己搞的楼房的编号
//单调栈
//单调栈存楼房下标
//找上一个或下一个更大的楼房高度
//没有则为-1#includeiostream
#includevector
#includestack
#includealgorithm
using namespace std;int N;//楼房数量
vectorint heights;//各楼房高度
vectorint res1,res2;//存储两个结果
stackint stk1,stk2;//单调栈//找左侧第一栋比自己高的楼房的编号
void leftFind(){//从左往右找 for(int i 0;i N;i){while(!stk1.empty()){if(heights[stk1.top()] heights[i]){stk1.pop();}else{res1.push_back(stk1.top());break;}}if(stk1.empty()){res1.push_back(-2);}stk1.push(i);}
} //找右侧第一栋比自己高的楼房的编号
void rightFind(){//从右往左找 for(int i N - 1;i 0;i--){while(!stk2.empty()){if(heights[stk2.top()] heights[i]){stk2.pop();}else{res2.push_back(stk2.top());break;}}if(stk2.empty()){res2.push_back(-2);}stk2.push(i);}//反转结果数组reverse(res2.begin(),res2.end());
}int main(){//输入整数数组 /*int t; while(cin.peek() ! \n){scanf(%d,t);nums.push_back(t);}*///输入楼房数量scanf(%d,N);//输入各楼房高度int h;for(int i 0;i N;i){scanf(%d,h);heights.push_back(h);} //-------------------------------//找左侧第一栋比自己高的楼房的编号leftFind(); //找右侧第一栋比自己高的楼房的编号rightFind();//输出结果//输出左侧第一栋比自己高的楼房的编号 for(int i 0;i res1.size();i){printf(%d ,res1[i] 1);} printf(\n);//输入右侧第一栋比自己高的楼房的编号for(int i 0;i res2.size();i){printf(%d ,res2[i] 1);} return 0;
}
总结 解题思路题目显然是要找上一个高大值和下一个更大值适合使用单调栈。
