首页 > 其他分享 >【经典题】栈和贪心法

【经典题】栈和贪心法

时间:2022-10-15 21:56:26浏览次数:72  
标签:arr int stack 数组 经典 mx 贪心

题目:769. 最多能完成排序的块

给定一个长度为 n 的整数数组 arr ,它表示在 [0, n - 1] 范围内的整数的排列。

我们将 arr 分割成若干 块 (即分区),并对每个块单独排序。将它们连接起来后,使得连接的结果和按升序排序后的原数组相同。

返回数组能分成的最多块数量。

示例 1:

输入: arr = [4,3,2,1,0]
输出: 1
解释:
将数组分成2块或者更多块,都无法得到所需的结果。
例如,分成 [4, 3], [2, 1, 0] 的结果是 [3, 4, 0, 1, 2],这不是有序的数组。

示例 2:

输入: arr = [1,0,2,3,4]
输出: 4
解释:
我们可以把它分成两块,例如 [1, 0], [2, 3, 4]。
然而,分成 [1, 0], [2], [3], [4] 可以得到最多的块数。

提示:

  • n == arr.length
  • 1 <= n <= 10
  • 0 <= arr[i] < n
  • arr 中每个元素都 不同

 

 

思路1:贪心法

每次遍历到最大值与下标相等,则可以完成一次分割,计数加1

T:O(n), S:O(1)

1 class Solution:
2     def maxChunksToSorted(self, arr: List[int]) -> int:
3         ans, mx = 0, 0
4         for i, v in enumerate(arr):
5             mx = max(v, mx)
6             if mx == i:
7                 ans += 1
8         return ans 

     

 

思路2:栈

利用栈先进后出的特性,完成栈内从小到大正序的排列

T:O(n), S:O(n)

 1 class Solution:
 2     def maxChunksToSorted(self, arr: List[int]) -> int:
 3         stack = []
 4         for i in arr:
 5             if not stack or stack[-1] < i:
 6                 stack.append(i)
 7             else:
 8                 mx = stack.pop()
 9                 while stack and stack[-1] > i:# 栈中只能保留最大值,例如arr = [4, 5, 0, 1, 2, 3], stack = [4, 5]时,遍历到0时,stack只能保留[5], 需要把4pop出去
10                     stack.pop()
11                 stack.append(mx)
12         return len(stack)

 

总结:贪心其实完成了每次记录最大值,stack是每次遍历时,stack中只能保留最大值,两者的本质其实一样。

 

标签:arr,int,stack,数组,经典,mx,贪心
From: https://www.cnblogs.com/wangpengcufe/p/16795149.html

相关文章

  • 逆向查找合并单元格中的数据,经典用法!
    Excel情报局职场联盟Excel生产挖掘分享Excel基础技能Excel爱好者大本营用1%的Excel基础搞定99%的职场问题做一个超级实用的Excel公众号Excel是门手艺玩转需要勇气数万Excel......
  • [NOIP2018 提高组] 铺设道路 贪心证明
    首先,这个是本蒟蒻第一次正经证明贪心,方法肯定有些繁琐(知识有限),仅作纪念。证明:记\(f(x)\)为序列中从第\(1\)到第\(x\)个数满足题意的最小天数。对于非上升序列\(\{a_1,a......
  • AtCoder Regular Contest 150 B Make Divisible 贪心 整除分块
    给出一个A和B想要找到一个X和Y使得\(A+X|B+Y\).同时使得X+Y最小求出X+Y的最小值。值域是\([1,10^9]\)直接枚举X不太行会被某种数据卡掉。考虑正解:先固定K另\(\frac{B......
  • Python人工智能经典算法之线性回归
    1.9k近邻算法总结[**]优点:1.简单有效2.重新训练代价底3.适合类域交叉样本4.适合大样本自动分类缺点:1.惰性学习2......
  • 贪心算法初讲1
     2.1.1贪心的基本思想:“只顾眼前”保证局部最优;贪心的特点:1.步步最优2.进行贪心策略的选择时要经过数学证明3.算法简单,选择一但做出不可回溯;   ......
  • 7.2 2叉树广度优先经典代码(C#)
     2叉树publicclassTreeNode{publicintval;publicTreeNodeleft;publicTreeNoderight;publicTreeNode(intx){val=x;......
  • 学一下贪心算法
    贪心算法思想在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,算法得到的是在某种意义上的局部最优解。特征1、贪心选择性质  一......
  • 大根堆+贪心算法
    前篇文章使用贪心算法求可达到最远建筑,还存在一些问题,只能取局部最优解。大根堆+贪心算法神偷Jacky身上带着一堆砖头和可以无限伸缩的梯子在楼顶穿梭。如果遇到下一......
  • 【第3版emWin教程】第50章 emWin6.x的AppWizard使用控件经典回调方式
    ​​​​第50章      emWin6.x的AppWizard使用控件经典回调方式本期教程为大家讲解emWin6.x的GUI开发工具AppWizard使用控件经典回调方式。这样我们就可以emWin的经......
  • 【BSP视频教程】STM32H7视频教程第14期:超干货,MPU和Cache实战,一张图了解所有经典配置案
    ​​​​ 本期视频给大家带来Cortex-M7内核MPU和Cache实战,各种经典常见案例分析。视频:​​​https://www.bilibili.com/video/BV1p54y1f7CY​​​一张图了解所有常见配置案......