LeetCode·2289. 使数组按非递减顺序排列·单调栈

news/2024/10/31 1:26:16/

作者:小迅
链接:https://leetcode.cn/problems/steps-to-make-array-non-decreasing/solutions/2213056/dan-diao-zhan-zhu-shi-chao-ji-xiang-xi-b-rvv0/来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

题目

 

思路

题意 -> 给定一个数组返回使得数组单独递增的最少操作数

  • 一次有效操作为:移除所有满足 nums[i - 1] > nums[i] 的 nums[i]

对于数组单调性题目,单调栈都是一个不错的辅助数据结构。

单调栈

  • 思路:
  1. 每个元素一定时被左侧第一个更大的元素消除的
  2. 设 x 消除 y,也就是 [x] .... [y],那么 中间的 .... 一定先被消除,再 +1 次消除(x 消除 y)
  3. 那么,x 被消除所需轮数就是 [....] 中的最大消除轮数 + 1
  • 具体实现:
    • 对应两个数组,一个用作 栈 - 保存左边第一个最大值下班,一个用于保存第 i 个数在第几次被移除。枚举所有元素,记录每一个元素的移除顺序,返回最大移除数。

代码注释超级详细

代码


int totalSteps(int* nums, int numsSize){int res = 0;int s[100001] = { 0 };  // 用单调栈存下标,用来找左边第一个大值int dp[100001] = { 0 }; // dp[i]: 第 i 个数在第dp[i]次被移除int top = 0;for (int i = 0; i < numsSize; ++i) { //枚举每一个元素      int cur = 0;while (top > 0 && nums[s[top - 1]] <= nums[i]) {//选择最近最大值cur = fmax(cur, dp[s[top - 1]]);//记录最大消除数top--;}if (top > 0) {//如果单调栈中有数据,那肯定比自己大,当前元素肯定会被移除,+1表示自己移除dp[i] = cur + 1;res = fmax(res, dp[i]);//保存最大数}s[top++] = i;}return res;
}作者:小迅
链接:https://leetcode.cn/problems/steps-to-make-array-non-decreasing/solutions/2213056/dan-diao-zhan-zhu-shi-chao-ji-xiang-xi-b-rvv0/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


http://www.ppmy.cn/news/40697.html

相关文章

docker安装vim报错E: Unable to locate package vim

原因&#xff1a;debian源不适用 解决方法&#xff1a; 1、更换镜像源&#xff1a; echo "deb http://mirrors.tuna.tsinghua.edu.cn/debian/ buster main contrib non-free" >/etc/apt/sources.list echo "deb http://mirrors.tuna.tsinghua.edu.cn/d…

C++--搜索二叉树的实现以及【原理详细讲解】+递归实现接口的代码

搜索二叉树搜索二叉树的定义插入查找遍历删除&#xff08;重点&#xff09;总结前言&#xff1a;文章中的代码大多以截图的形式呈现&#xff0c;文章的结尾处有二叉搜索树的代码链接。 搜索二叉树的定义 搜素二叉树&#xff1a; 若它的左子树不空&#xff0c;则左子树上所有结…

【Dev-c++】美化配置

概述 一个好的配置能够帮助开发者完成更便捷、更快速的开发书山有路勤为径&#xff0c;学海无涯苦作舟。我是秋知叶i、期望每一个阅读了我的文章的开发者都能够有所成长。 一、设置语法格式 点击工具 → 编辑器选项 选择 语法 点击预设这里选择 PlasticCodeWrap 只有第一…

【Java语法糖】泛型与源码角度分析静态问题

概念 首先聊聊泛型&#xff0c;泛型是JDK5的新特性。泛型是用来指定不同类型来控制形参具体限制的类型。泛型这种语法机制&#xff0c;只在程序编译阶段起作用&#xff0c;只是给编译器参考的&#xff08;运行阶段泛型没用&#xff09;。写了这么多代码应该能知道泛型的优点就是…

【01】PointNet论文解析

PointNet的应用 1.点云图像的分类&#xff08;整片点云是什么物体&#xff09; 2.点云图像的部件分割&#xff08;整片点云所代表的物体能拆分的结构&#xff09; 3.点云图像的语义分割&#xff08;将三维点云环境中不同的物体用不同的颜色区分开&#xff09; 补充 PointN…

( “树” 之 DFS) 226. 翻转二叉树 ——【Leetcode每日一题】

226. 翻转二叉树 给你一棵二叉树的根节点 root &#xff0c;翻转这棵二叉树&#xff0c;并返回其根节点。 示例 1&#xff1a; 输入&#xff1a;root [4,2,7,1,3,6,9] 输出&#xff1a;[4,7,2,9,6,3,1] 示例 2&#xff1a; 输入&#xff1a;root [2,1,3] 输出&#xff1a;[…

美颜技术的创新之路——美颜SDK的原理与应用探究

随着科技的不断发展&#xff0c;手机相机已经成为人们记录生活的重要工具。然而&#xff0c;拍照时的颜值问题却一直困扰着人们。为了解决这一难题&#xff0c;美颜技术应运而生。而美颜SDK作为美颜技术的一种应用&#xff0c;更是在不断地创新和发展中。本文将着重探究美颜SDK…

寻找CSDN平行世界的另一个你

本文由 大侠(AhcaoZhu)原创&#xff0c;转载请声明。 链接: https://blog.csdn.net/Ahcao2008 寻找CSDN平行世界的另一个你摘要前言列表测试目的摘要 本文作了一个测试&#xff0c;看看在 CSDN 的博文中&#xff0c;艾特&#xff08;&#xff09;某个好友&#xff0c;TA是否能够…