Leetcode 503.下一个更大元素
2024-10-22 12:20:13
下一个更大元素
给定一个循环数组(最后一个元素的下一个元素是数组的第一个元素),输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序,这个数字之后的第一个比它更大的数,这意味着你应该循环地搜索它的下一个更大的数。如果不存在,则输出 -1。
示例 1:
输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2;
数字 2 找不到下一个更大的数;
第二个 1 的下一个最大的数需要循环搜索,结果也是 2。
注意: 输入数组的长度不会超过 10000。
思路
使用栈来进行优化上面的算法,我们遍历两倍的数组,然后还是坐标i对n取余,取出数字,如果此时栈不为空,且栈顶元素小于当前数字,说明当前数字就是栈顶元素的右边第一个较大数,那么建立二者的映射,并且去除当前栈顶元素,最后如果i小于n,则把i压入栈。因为res的长度必须是n,超过n的部分我们只是为了给之前栈中的数字找较大值,所以不能压入栈,参见代码如下:
import java.util.Arrays;
import java.util.Stack; class Solution {
public int[] nextGreaterElements(int[] nums) {
int n=nums.length;
int[] res=new int[nums.length];
Arrays.fill(res,-1);
Stack<Integer> stack=new Stack<Integer>();
for(int i=0;i<2*n;i++){
int num=nums[i%n];
while(!stack.isEmpty()&&nums[stack.peek()]<num){
res[stack.peek()]=num;
stack.pop();
}
if(i<n) stack.push(i);
}
return res;
}
}
最新文章
- 《----css样式---------浮动带来的影响与解决方法---------------》
- HTML5的学习--performance
- bzoj 3518 Dirichlet卷积
- C#字符串处理(String与StringBuilder)
- 【Moqui业务逻辑翻译系列】Shipment Receiver Receives Shipment with Packing Slip but no PO
- 在mac上安装svn客户端
- Resilio-sync auto restart
- Java 文件句柄泄露问题解决小记
- 【转】QQ传输文件原理参考(来自互联网)
- asp.net core 系列之webapi集成Dapper的简单操作教程
- Centos 7.6搭建Tomcat 环境,发布Java项目
- thinkphp添加数据 add()方法
- MongoDB日志文件过大的解决方法
- 12C -- ORA-01033: ORACLE initialization or shutdown in progress
- kali linux 入侵window实例
- Zookeeper的Watcher机制
- 51nod-1298 圆与三角形(计算几何超详解)
- jersey中的405错误 method not allowed
- NFV/SDN驱动OSS转型
- Python学习---Django重点之静态资源配置
热门文章
- StackOverflow之旅<;1>;------{去掉烦人的";!=null";判断}
- Android(java)学习笔记91:Eclipse中代码提示去掉@override,不然就报错!
- 2018.5.19 Oracle数据操作和管理表的综合练习
- javaweb基础(31)_国际化(i18n)
- js转换时间戳成日期格式
- 如何利用WordPress的菜单功能实现友情链接功能?
- vuex:使用思路总结
- macOS如何正确驱动集成显卡HDMI(包括视频和音频)
- 1305: [CQOI2009]dance跳舞
- mysql 删除 一天前 创建 的数据,计算时间差