1. Job Roadmap
  2. Home
  3. Problem Set
  4. codenotelist
  5. Forum
  6. course
  7. Shore Share Sessions
  8. Record
  1. Login
  2. Sign Up
  3. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
    ZhContent TextSol AI分析

解题思路

本题可以使用单调栈解决。

对于每个元素 nums[i]nums[i]nums[i],我们需要判断它会在第几轮被删除。

从左到右遍历数组,维护一个单调递减趋势相关的栈,栈中保存:

  • 元素值

P4902.使数组按非递减顺序排列

    1000ms Tried: 29 Accepted: 10 Difficulty: 5 所属公司 : Hot100
    算法与标签>栈

题目描述

给定一个长度为 nnn 的整数数组 numsnumsnums。

在一步操作中,需要同时移除所有满足 nums[i−1]>nums[i]nums[i - 1] > nums[i]nums[i−1]>nums[i] 的元素 nums[i]nums[i]nums[i],其中 1<=i<n1 <= i < n1<=i<n。

重复执行上述操作,直到数组 numsnumsnums 变为非递减数组。

请输出使数组变为非递减数组所需执行的操作次数。

输入描述

第一行输入一个整数 nnn,表示数组 numsnumsnums 的长度。

第二行输入 nnn 个整数,表示数组 numsnumsnums 中的元素。

输出描述

输出一个整数,表示使数组 numsnumsnums 变为非递减数组所需执行的操作次数。

样例 111

输入

11
5 3 4 4 7 3 6 11 8 5 11

输出

3

解释

执行下述几个步骤:

  • 步骤 111:[5,3,4,4,7,3,6,11,8,5,11][5,3,4,4,7,3,6,11,8,5,11][5,3,4,4,7,3,6,11,8,5,11] 变为 [5,4,4,7,6,11,11][5,4,4,7,6,11,11][5,4,4,7,6,11,11]
  • 步骤 222:[5,4,4,7,6,11,11][5,4,4,7,6,11,11][5,4,4,7,6,11,11] 变为 [5,4,7,11,11][5,4,7,11,11][5,4,7,11,11]
  • 步骤 333:[5,4,7,11,11][5,4,7,11,11][5,4,7,11,11] 变为 [5,7,11,11][5,7,11,11][5,7,11,11]

[5,7,11,11][5,7,11,11][5,7,11,11] 是一个非递减数组,因此,输出 333。

样例 222

输入

5
4 5 7 7 13

输出

0

解释

numsnumsnums 已经是一个非递减数组,因此,输出 000。

数据范围

  • 1<=n<=1051 <= n <= 10^51<=n<=105
  • 1<=nums[i]<=1091 <= nums[i] <= 10^91<=nums[i]<=109

登录后即可使用 AI 分析。

模式
倒计时时长
:

最长 10 小时 59 分;应用后按此时长重新开始。

提示:点击提交记录在左侧题面区域查看详情
题库
AI分析设置
留空使用官方API Key,每天有次数限制(自定义API Key仅限会员和管理员使用,不限次数)
会员和管理员可切换模型;切到 Kimi/智谱/通义/豆包时需填写对应供应商 API Key
升级会员,可将运行与提交冷却时间缩短至 1 秒起

Status

  • Judging Queue
  • Service Status

Development

  • Open Source

Support

  • Help
  • Contact Us

About

  • About
  • Privacy
  • Terms of Service
  • Copyright Complaint
  1. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
  2. Legacy mode
  3. Theme
    1. Light
    2. Dark
  1. 京ICP备2025123107号-1
  2. Worker 0, 34ms
  3. Powered by Hydro v5.0.0-beta.18 Community
CLOSE


ScanQRCodePrompt

请使用微信扫描下方二维码完成注册

Forgot password or username?