当前位置:网站首页>leetcode 503.下一个更大元素II 单调栈
leetcode 503.下一个更大元素II 单调栈
2022-08-09 18:05:00 【Alkali!】
题目描述
思路
利用单调栈的思想
- 这里要处理的数组是循环数组,但是输出的时候,还是输出原数组对应的答案,所以可以先进行处理,将原数组转化为一个伪循环数组。
即将数组 [ 0... n − 1 ] [0...n-1] [0...n−1]转化为数组[0…n-1,0…n-2] - 利用单调栈思想进行处理整个数组,从后往前处理,因为题目让求得是每个元素的 下一个更大元素
单调栈思想参考 - 将答案翻转,去掉尾部伪循环数组的部分,return结果
代码
#include<algorithm>
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
stack<int> s;
vector<int> res;
//将原数组后面添上循环的内容,变为线性伪循环数组
int length=nums.size();
for(int i=0;i<length-1;i++)
nums.push_back(nums[i]);
//从后往前遍历伪循环数组,利用单调栈的思想进行处理
for(int i=nums.size()-1;i>=0;i--)
{
while(!s.empty()&&s.top()<=nums[i])
s.pop();
if(s.empty()) //如果不存在,则输出 -1
res.push_back(-1);
else
res.push_back(s.top());
s.push(nums[i]);
}
//对结果的处理
reverse(res.begin(),res.end());
for(int i=0;i<length-1;i++)
res.pop_back();
return res;
}
};
边栏推荐
- 100+开箱即用的AI工具箱;程序员150岁长寿指南;『地理空间数据科学』课程资料;Graphic数据可视化图表库;前沿论文 | ShowMeAI资讯日报
- PHP 变量注释/**@var*/
- An overview of Office 365 Groups and how to create them
- 对数学直观、感性的认知是理解数学、喜爱数学的必经之路,这本书做到了!
- Sublime Text的安装过程记录
- 5.4 总结
- How to stop the test after reaching a given number of errors during stress testing in JMeter
- [免费专栏] Android安全之和平精英(FZ)APK逆向分析
- 对应运放 RC 滤波负反馈的波形
- AWK使用
猜你喜欢
uniapp离线推送华为厂商申请流程
阿里云张新涛:支持沉浸式体验应用快速落地,阿里云云XR平台发布
YOLO v3 source, rounding
Iptables防火墙常见的典型应用场景
How to play with container local storage through open-local? | Dragon Lizard Technology
使用.NET简单实现一个Redis的高性能克隆版(四、五)
Cortex-A7 MPCore Architecture
[免费专栏] Android安全之APK动态方式逆向应用【三种Smali注入方法】
每周给我10分钟,我给你一个Flink SQL 菜谱——甜点:数据过滤
loadrunner script -- parameterization
随机推荐
全自动化机器学习建模!效果吊打初级炼丹师!
什么是ROS
一些自动化测试01
C#/VB.NET:从PowerPoint文档中提取文本和图片
哈希表
三星旗舰优惠千八,苹果优惠过千,国产旗舰只降五百打发叫花子
面试官:当Redis大的时候,要如何处理key?
YOLO v3源码详解
开源一夏 | 基于若依架构的列表详情展示
牛客网 Verilog 在线编程题库解答(VL1~VL10)
正则表达式(全)
Mysql table structure change scheme comparison and analysis
golang单元测试:testing包的基本使用
从功能测试到自动化测试你都知道他们的有缺点吗?
2022.08.08_每日一题
Fully automated machine learning modeling!The effect hangs the primary alchemist!
什么是藏宝计划(TPC),2022的一匹插着翅膀的黑马!
grafana docks local ldap
安装搭建私有仓库 Harbor
[免费专栏] Android安全之Android Studion 动态调试APK的两种方法